[BOJ 12851] 숨바꼭질 2 (Java)

BOJ 12851 숨바꼭질 2

문제풀이

간단한 문제라고 생각하고 바로 BFS로 풀이를 시작했으나 여러가지 문제에 부딪혔다.
1. 어떻게 최소시간에 도착한 경우만 카운트할 것인가?
- 가장 먼저 도착했을 때 큐에 들어있는 경우까지만 카운트하면 된다.
2. 같은 위치에 도달하더라도 다른 방법으로 도달할 수 있다.
- 이전의 위치를 기억하기 위해 boolean[][] visited로 2차원을 사용하기로 했다.
- 하지만 10만 * 10만 = 100억이다... 메모리초과!
- 생각해보니 같은 시간(최소)에 도착하는 것만 카운트하면 되니 큐에 들어가기만 하면 된다. 따라서 큐에 넣을 때 방문체크를 하지말고 큐에서 꺼낼 때 방문체크 하자!(늦은 방문 체크)

구현코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static boolean[] visited;
	static Queue<Integer> q;
	static int N, K;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
		
		visited = new boolean[100001];
		q = new LinkedList<>();
		
		q.offer(N);
		visited[N] = true;
		
      	// 이미 같이 있는 경우
		if(N == K) {
			System.out.println(0);
			System.out.println(1);
			return;
		}
		
		bfs();
	}

	private static void bfs() {
		int time = 0;
		int cnt = 0;
		
		while(!q.isEmpty()) {
			int size = q.size();
			time++;
			for(int i = 0 ; i < size ; ++i) {
				int cur = q.poll();
				// 꺼낼 때 방문체크 하므로써 다른 방법으로 같은 시간에 도착한 경우들을 허용한다.
				visited[cur] = true;
				
				int[] next = {cur - 1, cur + 1, cur * 2};
				for(int j = 0 ; j < 3 ; ++j) {
					if(next[j] >= 0 && next[j] <= 100000 && !visited[next[j]]) {
						if(next[j] == K) {
							cnt++;
							continue;
						}
//						visited[cur][next[j]] = true;
						q.offer(next[j]);
					}
				}
			}
			// cnt가 올라간건 최소시간에 도착했다는 것으로 이후 시간에 도착하는 것은 무의미하다.
			if(cnt != 0) q.clear();
		}
		System.out.println(time);
		System.out.println(cnt);
	}
}