[백준] 1697번 - 숨바꼭질

 

1697번: 숨바꼭질

 

 

특정 시점에서 수빈이의 위치가 X일 때, 수빈이가 1초 후에 이동할 수 있는 위치는 X-1, X+1, X*2 세군데이다.

0부터 100000까지의 정수를 각각 정점으로 보고 특정 수 X 기준 X-1, X+1, X*2를 방문처리하면서 시간을 1초씩 증가시키며 정점을 순회하는 방식으로 접근하면 문제를 해결할 수 있다. 이때 BFS를 사용하여 도달하는데 걸리는 최소 시간이 작은 위치먼저 방문처리를 한다. 

 

 

 

수빈이의 시작 위치가 5이고, 동생의 위치는 12인 경우를 살펴보자.

 

1초 후 수빈이가 존재할 수 있는 위치는 4, 6, 10이다. 특정 위치 x에 수빈이가 도달하는데 걸리는 최소 시간을 기록한 배열을 time[]이라고 할 때 time[4], time[6], time[10]에는 값 1 이 들어간다.

 

그 다음 4, 6, 10에서 수빈이가 이동할 수 있는 위치는 각각 (3, 5, 8), (5, 7, 12), (9, 11, 20)인데 이 위치들 중에서

time[x] != 0 에 해당하는 위치는 이미 방문한 위치로, 해당 위치에 도달하는데 걸리는 최소 시간을 알고 있는 위치이므로 다시 방문할 필요가 없다. 따라서 time[3], time[8], time[7], time[12], time[9], time[11], time[20] 에 값 2 가 들어간다.

 

여기서 찾고자 하는 동생의 위치가 12 이므로, 수빈이가 동생을 찾는데까지 걸리는 최소 시간은 time[12] = 2 가 된다. 

 

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int N, K;
    static int[] time;
    static Queue<Integer> que;
    
    static int MAX = 100000;
    static int MIN = 0;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        time = new int[100001];
        
        String[] input = br.readLine().split(" ");
        
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        
        System.out.println(bfs(N));
        
        br.close();
    }
    
    static int bfs (int subin) {
        
        que = new LinkedList<>();
        
        time[subin] = 0;
        que.offer(subin);
        
        while (!que.isEmpty()) {
            
            int n = que.poll();
            
            // 수빈이가 동생을 찾으면 while 종료 후 time[K]를 리턴한다.
            if (n == K) break;
            
            int next = time[n] + 1;
            
            // 현재 n에 있는 수빈이가 1초 후 이동할 수 있는 3가지 위치
            if (n+1 <= MAX && time[n+1] == 0) {
                time[n+1] = next;
                que.offer(n+1);
            }
            if (n-1 >= MIN && time[n-1] == 0) {
                time[n-1] = next;
                que.offer(n-1);
            }
            if (n*2 <= MAX && time[n*2] == 0) {
                time[n*2] = next;
                que.offer(n*2);
            }
        }
        
        return time[K];
    }
}