1697 : 숨바꼭질

출처 : https://www.acmicpc.net/problem/1697

---

문제

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

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

입력

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

출력

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

---

접근

• 현재 index를 기준으로 접근 가능한 모든 index를 참조해야 하므로, BFS 알고리즘을 이용하기로 했다. 
• BFS 함수는 1회 호출되고, 함수 내부의 while문이 N과 K값이 같아질 때까지 반복하도록 하였다. 
• 현재 N을 기준으로 접근 가능한 nextN을 탐색한다.
• nextN이 K와 다르다면, nextN을 queue에 넣고, nextN을 N으로 한다.

---

코드

 

package beak;
 
import java.util.*;
import java.io.*;
 
public class Beak01697 {
    static int N, K;
    static int[] List = new int[100005];
 
    public static int BFS() {
        int nextN = N;
        int[] nextStatus = new int[3];    // 다음으로 이동 가능한 좌표를 담는 리스트 
        
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(nextN);
        List[nextN] = 0;
 
        while (!q.isEmpty() && nextN != K) {
            nextN = q.poll();
 
            nextStatus[0] = nextN - 1;
            nextStatus[1] = nextN + 1;
            nextStatus[2] = nextN * 2;
 
            for (int i = 0; i < 3; i++) {
                if (nextStatus[i] >= 0 && nextStatus[i] <= 100000) {
                    if (List[nextStatus[i]] == -1) {
                        q.add(nextStatus[i]);
                        List[nextStatus[i]] = List[nextN] + 1;
                    }
                }
            }
        }
        return List[K];
    }
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        Arrays.fill(List, -1); // 초기값을 다 -1로 설정
 
        bw.write(BFS() + "\n");
 
        bw.flush();
        br.close();
    }
}