[백준] G5 13549 숨바꼭질 3 (java)

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

풀이

 

1) 방문체크할 visited[] 배열을 만듬. 사이즈는 200001. N이 최대 10만이고 * 2 하면 20만이 나올 수 있으므로.

2) bfs를 돈다 class의 멤버는 cnt

2-1) X = 2 * X : cnt = cnt

2-2) X = X - 1 : cnt = cnt + 1

2-3) X = X + 1 : cnt = cnt + 1

3) X = K 가 되면 끝

4) cnt 출력

 

주의사항

 

1) 반드시 곱하기 -> 빼기 -> 더하기 순서여야만 함

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_13549_숨바꼭질3 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,K;
	static boolean isVisited[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		isVisited = new boolean[200001];
		
		bfs(N);
	}

	private static void bfs(int n) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(n, 0));
		isVisited[n] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(front.num == K) {
				System.out.println(front.cnt);
				return;
			}
			if(isIn(front.num*2) && !isVisited[front.num * 2]) {
				queue.offer(new Node(front.num * 2, front.cnt));
				isVisited[front.num * 2] = true;
			}
			if(isIn(front.num-1) && !isVisited[front.num-1]) {
				queue.offer(new Node(front.num-1, front.cnt+1));
				isVisited[front.num-1] = true;
			}
			if(isIn(front.num+1) && !isVisited[front.num+1]) {
				queue.offer(new Node(front.num+1, front.cnt+1));
				isVisited[front.num+1] = true;
			}
		}
	}

	static boolean isIn(int n) {
		return (n>=0 && n<100001);
	}
	
	static class Node{
		int num;
		int cnt;
		public Node(int num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}
	}
	
	static String src =
			"0 2";
}

 

후기

 

 10번이나 틀렸다. 더럽게 어렵다. 아직도 왜 -와 +의 순서가 중요한지 이해가 안간다. 젠장..

이 문제는 사실 다익스트라 문제라고한다. 저번부터 느끼지만 난 bfs, dfs 빼고 할줄아는게 없는 머저리이다.

그리디, dp, 다익스트라, 해시등을 위주로 문제를 풀어야겠다고 다시한번 느꼈다. 

배운점 : 일반적인 bfs를 쓰려면 가중치가 같아야 함.