[백준] 1697번 : 숨바꼭질

1697번: 숨바꼭질

# 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

# 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

# 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

# 예제 입력 1

5 17

# 예제 출력 1

4

 

# 알고리즘 분류

• 그래프 탐색
• 그래프 이론
• BFS

---

너비 우선 탐색 방법을 이용하여 한 정점에서 다른 정점까지의 최단 거리를 구하는 방법은 대부분 비슷하게 푸는 것 같다. 시작 정점 -> 갈 수 있는 정점들 -> 갈 수 있는 정점들 -> ... -> 목표 정점 이라는 매커니즘 속에 적절한 조치만 취해주면 구할 수 있는 것 같다.

 

시작 정점 N에서 목표 정점 K까지의 최단 경로를 구해보자. (단, 0<= N, K <= 100,000) 정점 N에서 다음 방문할 수 있는 정점은 N+1, N-1, N*2인 정점이다. 단, 반드시 0 <= N+1, N-1, N*2 <= 100,000 조건을 지켜야만 한다. 그렇지 않으면 런타임에러나, 인덱스 에러를 마주하게 된다. 그리고 한 번 방문했던 정점은 다시 방문해서 값을 변경시키면 안된다. 최단 경로를 구해야 하기 때문이다.

 

간단하게 2에서 13으로 가는 최단경로 구하는 것을 예로 들어보려 한다. 아마 2->3->6->12->13이 최단 경로가 아닐까 싶다.

 

(1) 초기 배열은 모두 0이고, 시작 정점인 정점 2에서 시작한다는 뜻으로 정점 2=1

arr[100,001] = [0, 0, 1, 0, 0, 0, 0, 0, ... , 0]

---

(2) 정점 2는 다음 정점을 갈 수 있다.

front = 3

back = 1

warp = 4

세 정점 방문하지 않았고 모두 0 이상 100,000이하 이므로 OK, 2로 세팅한다.

∴ arr[] = [0, 2, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, ..., 0]

---

(3 - 1) 정점 3은

front = 4 //이미 방문

back = 2 //이미 방문

warp = 6 

이므로 정점 6만 방문 가능하다. 

 

(3 - 2) 정점 1은

front = 2 //이미 방문

back = 0

warp = 2 //이미 방문

이므로 정점 0만 방문 가능하다.

 

(3 - 3) 정점 4는

front = 5

back = 3 //이미 방문

warp = 8

이므로 정점 5, 8 방문 가능하다.

∴ arr[] = [3, 2, 1, 2, 2, 3, 3, 0, 3, 0, 0, 0, ..., 0]

---

(4 - 1) 정점 6

front = 7 

back = 5 //이미 방문

warp = 12

이므로 정점 7, 12 방문 가능하다.

 

(4 - 2) 정점 0

front = 1 //이미 방문

back = -1 //범위 초과

warp = 0 //이미 방문

이므로 방문 가능한 곳이 없다.

 

(4 - 3) 정점 5

front = 6 //이미 방문

back = 4 //이미 방문

warp = 10

이므로 정점 10만 방문 가능하다.

 

(4 - 4) 정점 8

front = 9

back = 7 

warp = 16

이므로 정점 7, 9, 16 모두 방문 가능하다.

∴ arr[] = [3, 2, 1, 2, 2, 3, 3, 4, 3, 4, 4, 0, 4, 0, 0, 0, 4, 0, ..., 0]

---

 

(5 - 1) 나머진 생략하고 정점 12에서만 생각해본다...ㅠ

front = 13

back = 11

warp = 24

이므로 모든 정점 방문 가능하다. 이 중에서 front = 13이므로 우리가 목표로 하는 정점 13에 도달하는데 걸리는 경로 수는 5이다. 그런데 시작할 때 카운팅한 1은 빼야 하므로 5 - 1인 4가 답이 된다.

---

# Whole Code </>

public class Main {

    static final int MAX = 1000001;
    static int[] arr = new int[MAX];

    static Queue<Integer> Q = new LinkedList<>();
    static void BFS(int n, int k){

        arr[n] = 1;
        Q.add(n);

        while(!Q.isEmpty() && arr[k] == 0) {
            int present = Q.poll();
            //System.out.println("현재 : " + present + ", arr["+present+"] = " + arr[present]);

            int front = present + 1;
            int back = present - 1;
            int warp = present * 2;

            if(front >= 0 && front < MAX)
                if(arr[front] == 0){
                    arr[front] = arr[present] + 1;
                    Q.add(front);
                }
            if(back >= 0 && back < MAX)
                if(arr[back] == 0){
                    arr[back] = arr[present] + 1;
                    Q.add(back);
                }
            if(warp >= 0 && warp < MAX)
                if(arr[warp] == 0) {
                    arr[warp] = arr[present] + 1;
                    Q.add(warp);
                }
        }
        System.out.println(arr[k]-1);
    }
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        StringTokenizer stk = new StringTokenizer(str);

        int n = Integer.parseInt(stk.nextToken());
        int k = Integer.parseInt(stk.nextToken());

        BFS(n, k);
    }
}