[백준 / BOJ] 12851번 : 숨바꼭질 2 (JAVA)

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

동생이 수빈이보다 낮은 숫자에 있는 경우 (N  >  K)

BFS를 시도하기 전에 먼저 생각해둬야 할 것이 있다. 동생이 있는 K가 수빈이가 있는 N에 비해 작은 수라면 어떻게 될까? 이동할 수 있는 경우의 수가 한 칸 전진, 숫자가 두 배인 칸 가기, 한 칸 후퇴 세 가지밖에 없는 상황에서, K가 더 작다면 수빈이는 매번 -1만 진행해야 한다. 앞으로 한 칸을 가든, 현재 칸의 두 배인 숫자로 가든 다시 돌아가야 하는 칸 수만 늘어날 뿐이기 때문이다.

 

따라서 N과 K를 입력받은 후 만일 N > K라면 N - K가 최소 시간, 그리고 그렇게 가는 경우의 수는 단 하나(계속 -1만 하는 것)밖에 없다고 출력하도록 했다. 그 다음 단계로 넘어가면 안되기 때문에 System.exit(0)으로 정상 종료하였다.

if(N > K) { // 만일 수빈이가 동생보다 큰 수에 있다면
    System.out.println(N - K);
    System.out.println(1);
    System.exit(0);
}

 

K에 도달했을 때

이제 BFS로 최소 시간을 구해야 한다. 움직일 수 있는 세 가지 경우의 수를 que에 넣어가며 K에 도달할 때까지 돌리는 것은 쉬운데, 최소 시간을 사용하는 경우의 수가 몇 개인지까지 찾으려면 조건이 조금 더 추가된다.

 

먼저 K에 도달했을 때를 살펴보자.

int[] cur = que.poll();
int loc = cur[0];
int t = cur[1];

if(t > time) continue;
if(loc == K) { // 동생 찾으면
    if(time == t) { // 최소 경로라면
        cnt++;
    } else if(time > t) { // 지금까지보다 더 최소 경로라면
        time = t;
        cnt = 1;
    }
    continue;
}

K에 도달하면 일단 시간이 얼마나 걸렸는지 확인한다. 지금까지보다 더 빨리 도착했다면 time을 교체하고 cnt도 1로 변경한다. 그게 아니라 현재까지의 최소 시간과 같다면 cnt만 늘려준다.

 

BFS이기 때문에 어차피 가장 먼저 loc == K 조건에 걸린 게 최소 시간일 테니, time > t라는 조건은 필요가 없을 수도 있다. 이것 말고 flag를 둔다거나, time이 Integer.MAX_VALUE인 경우에는 time을 t로 변경한다든가 하는 조건을 사용해도 무방하다.

 

K에 이미 도달했기 때문에 따로 더 이동할 필요가 없어 continue로 이후 단계를 스킵했다.

 

K로 가는 경로 찾기

다음에 갈 곳을 Queue에 넣고 방문 체크를 하면 된다. 다만 주의할 것은, '최소 시간'만 구하는 것이 아니라 최소 시간을 사용하는 경우의 수를 찾는 것이기 때문에 이미 방문한 곳이라고 무작정 뺄 수는 없다.

if(loc + 1 <= 100000 && (v[loc + 1] == 0 || v[loc + 1] >= t)) { // +1 이동
    v[loc + 1] = t;
    que.offer(new int[] {loc + 1, t + 1});
}

if(loc - 1 >= 0 && (v[loc - 1] == 0 || v[loc - 1] >= t)) { // -1 이동
    v[loc - 1] = t;
    que.offer(new int[] {loc - 1, t + 1});
}

if(loc * 2 <= 100000 && (v[loc * 2] == 0 || v[loc * 2] >= t)) { // *2 이동
    v[loc * 2] = t;
    que.offer(new int[] {loc * 2, t + 1});
}

따라서 다음에 갈 곳이 주어진 범위(0 ~ 100000) 안인지 먼저 확인한 후, 방문할 수 있을지 다시 확인했다.

 

일단, 한 번도 방문해 본 적이 없는 곳이라면 당연히 가능하다. v[loc + 1] == 0

만일 방문해 본 적이 있더라도, 지금 내가 걸린 시간이 그곳까지 가는 데에 걸리는 최소 시간과 같다면 또 다시 방문 가능하다.

 

즉, v[3]에 4라 적혀 있었다고 해보자. 이 뜻은 3번 칸을 4번만에 갈 수 있다는 뜻이다. 그리고 이번의 t가 4라면, 이번 역시 3번 칸을 최소 횟수로 도착했기 때문에 방문 가능하다.

 

 

전체 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {N, 1}); // 방문 체크를 위해 1부터 시작 -> 나중에 답 출력 시 1 빼줌
		
		int cnt = 0; // 최소 루트로 도달하는 경우의 수
		int time = Integer.MAX_VALUE; // 최소 루트
		
		int[] v = new int[100001]; // 방문 체크
		v[N] = 1;
		
		
		if(N > K) { // 만일 수빈이가 동생보다 큰 수에 있다면
			System.out.println(N - K);
			System.out.println(1);
			System.exit(0);
		}
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int loc = cur[0];
			int t = cur[1];
			
			if(t > time) continue;
			if(loc == K) { // 동생 찾으면
				if(time == t) { // 최소 경로라면
					cnt++;
				} else if(time > t) { // 지금까지보다 더 최소 경로라면
					time = t;
					cnt = 1;
				}
				continue;
			}
			
			
			if(loc + 1 <= 100000 && (v[loc + 1] == 0 || v[loc + 1] >= t)) { // +1 이동
				v[loc + 1] = t;
				que.offer(new int[] {loc + 1, t + 1});
			}
			
			if(loc - 1 >= 0 && (v[loc - 1] == 0 || v[loc - 1] >= t)) { // -1 이동
				v[loc - 1] = t;
				que.offer(new int[] {loc - 1, t + 1});
			}
			
			if(loc * 2 <= 100000 && (v[loc * 2] == 0 || v[loc * 2] >= t)) { // *2 이동
				v[loc * 2] = t;
				que.offer(new int[] {loc * 2, t + 1});
			}
		}
		
		System.out.println(time - 1);
		System.out.println(cnt);
	}

}