[BOJ] 1697 : 숨바꼭질(Java)

문제

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

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

입력

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

출력

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

---

💡풀이

주어진 N에 대해 $(N-1), (N+1), (2*N)$을 N에 인접한 노드라 생각하면 그래프가 그려질 것이다. 이를 BFS를 이용해 목표 지점인 K까지의 최단 거리를 구하는 방법을 사용하면 된다.
 int형 배열 node에 $\{cur-1, cur+1, cur*2\}$를 넣고 이를 큐(Queue)에 넣어 BFS를 시도했다. 각 노드에 해당하는 거리의 정보를 입력하는 $distance$배열을 처음에 -1로 초기화 시켜주고, 이를 이용해 방문 체크를 하였다($distance[next]==-1$이면 방문하지 않은 노드). 

이때 주의할 점은 각 node의 범위인데, 문제에 주어진 N의 범위를 그대로 이용해, $0<=node<100,001$로 설정하였다. 만약 $K$와 같은 노드가 발견된다면 $distance[node]$를 출력하고 종료한다. 

 

전체 코드는 다음과 같다.

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

public class Q1697 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] distance = new int[100001];
        Arrays.fill(distance, -1);
        Queue<Integer> queue = new LinkedList<>();
        distance[N] = 0;
        queue.offer(N);

        while(!queue.isEmpty()){
            int cur = queue.poll();
            int[] node = new int[]{cur-1, cur+1, cur*2};

            for(int next:node){
                if(next>=0 && next<100001 && distance[next] == -1) {
                    distance[next] = distance[cur] + 1;
                    queue.offer(next);
                }
                if(next == K){
                    System.out.println(distance[next]);
                    return;
                }
            }
        }
    }
}