[백준 1697번] 숨바꼭질 - BFS

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

오랜만에 bfs 문제를 만나게 됐네요 ㅎㅎㅎ

 

처음에 낸 풀이는 메모리 초과가 떴습니다. 문제는 방문한 노드들을 체크하는 시점 때문에 발생한 문제였는데요.

예를 들면 dfs에서는 노드를 방문하고 나서야 현재 노드에 방문 체크를 하게 됩니다. 하지만 bfs는 방문 이전 시점, 즉 이전 노드에 의해 큐에 추가 될때 이미 방문 체크를 해버립니다.

 

왜 이렇게 하는가? 라는건 조금만 생각해보면 알 수 있습니다. 

만약 같은 깊이에 있는 A와 B가 동일한 자식 노드 C를 가지고 있다고 할 때, 방문하고 나서야 체크를 한다면 A,B 둘 다 C를 큐에 넣게 됩니다. 이는 부모가 다르더라도 중복입니다. 부모가 다르더라도 깊이(거리)가 같다면 차이가 의미가 없기 때문입니다.

 

 

 

...

/*
백준 1697번 - 숨바꼭질
https://www.acmicpc.net/problem/1697
 */
public class Main {
	static int n,k;
	static boolean[] discovered = new boolean[100001];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		bfs(n,k);
	}

	private static void bfs(int start, int destination) {
		Queue<Node> q = new ArrayDeque<>();
		q.add(new Node(start, 0));
		discovered[start] = true;

		while(true) {
			Node here = q.poll();

			if(here.n == destination) {
				System.out.println(here.distance);
				break;
			}

			int walkLeft = here.n-1;
			int walkRight = here.n+1;
			int jump = here.n*2;
			int[] arr = {walkLeft, walkRight, jump};
			Arrays.stream(arr)
					.filter(n -> isRange(n))
					.filter(n -> !discovered[n])
					.forEach(n -> {
						q.add(new Node(n, here.distance+1));
						discovered[n] = true;
					});
		}
	}

	private static boolean isRange(int n) {
		if(n >= 0 && n <= 100000) return true;
		return false;
	}

}
class Node {
	int n, distance;

	public Node(int n, int distance) {
		this.n = n;
		this.distance = distance;
	}
}