백준 1697. 숨바꼭질 (JAVA)

○ 문제 요약

수빈이가 동생의 위치로 간다고 할 때, 가장 적은 시간이 걸리는 방법의 시간을 출력해라.

○ 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        if(N >= K){
            System.out.println(N - K);
        }else{
            System.out.println(bfs(N,K));
        }

    }

    public static int bfs(int N, int K){
        Queue<Integer> q = new LinkedList<>();
        int[] arr = new int[100001];

        q.offer(N);
        arr[N] = 1;

        while(!q.isEmpty()){
            int now = q.poll();

            for(int i = 0 ; i < 3; i++){
                int next;

                if(i==0){
                    next = now - 1;
                }else if(i == 1){
                    next = now + 1;
                }else{
                    next = now * 2;
                }

                if(next == K){
                    return arr[now];
                }

                if(0 <= next && next < 100001){
                    if(arr[next] == 0){
                        q.offer(next);
                        arr[next] = arr[now] + 1;
                    }
                }
            }
        }
        return 0;
    }

}

 

알고리즘 분류가 너비 우선 탐색이라고 명시되어 있었지만 그럼에도 코드를 작성하는 것이 쉽진 않았다.

 

Queue를 생성해주고 값을 저장할 배열도 하나 생성해주었다. 이 배열은 인덱스로 연산하고 나온 값을 가지고 값은 몇 초가 지났는지 알 수 있도록 초를 넣어줄 것이다. 아무래도 글로 설명하는 것보다 그림으로 보는 것이 빠른 이해를 도와주므로 그림으로 보자.

now가 5일 때, arr 배열에 위 그림과 같이 값이 들어가고 Queue에는 4, 6, 10이 들어간다. 

 

 

문제에서는 힌트로 5 -> 10 -> 9 -> 18 -> 17 경로를 주었지만 5 -> 4 -> 8 -> 16 -> 17도 가능하다는 것을 알았다.

 

next와 k가 같아졌으므로 아래 조건식이 성립한다.

어떤 경로로 17이라는 값이 되었든지 arr[16]이나 arr[18] 모두 4라는 값을 갖는 것은 같으므로 arr[16]나 arr[18]이 출력되면 4초 뒤에 수빈이와 동생이 같은 위치에 있다는 것을 알 수 있다.

 

○ 결과