[JAVA] 백준 1697 숨바꼭질

[백준 1697]https://www.acmicpc.net/problem/1697

---

문제 조건

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
수빈이의 위치가 X일 때 3가지 선택을 할 수 있다. 세 선택 모두 1초가 걸린다.
1. X-1로 이동
2. X+1로 이동
3. 2×X의 위치로 이동

수빈이가 동생을 찾을 수 있는 가장 빠른 시간은 몇 초 후인가?

---

문제 입력

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

---

문제 풀기 전 설계

DP문제라기엔 중복되는 게 없는 것 같은데 어떻게 풀어야할까
모든 좌표를 그래프의 정점으로 생각하고 각각의 이동을 간선으로 이어주면 N에서 K까지의 최단거리를 구하는 그래프 문제가 된다.
그래프의 최단거리 -> BFS(너비우선탐색)

---

문제 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int n;
    static int k;

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

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        if (n >= k) {
            // n이 k 이상이면 최단거리는 (n-k)번 -1 이동
            System.out.println(n - k);
        }
        else {
            // 이외에는 bfs
            bfs();
        }

    }

    private static void bfs() {
        int[] time = new int[100001];   // 소요 시간 저장하는 배열
        boolean[] isVisit = new boolean[100001];    // 정점을 탐색했는지 체크하는 배열
        Queue<Integer> queue = new LinkedList<>();  // bfs 구현 위한 Queue
        isVisit[n] = true;
        queue.offer(n);
        time[n] = 1;    // int형 배열은 초기값이 0이라서 초기 시간으로 1을 넣어줌

        while (!queue.isEmpty()) {
            int num = queue.poll();

            for (int i = 0; i < 3; i++) {   // 한 정점에서 -1, +1, *2인 정점이 인접 노드
                int nextNum;

                if (i == 0) nextNum = num + 1;
                else if (i == 1) nextNum = num - 1;
                else nextNum = num * 2;

                if (nextNum == k) { // 인접 노드로 k를 가지고 있으면 탐색 종료
                    System.out.println(time[num]);
                    return;
                }

                if (nextNum >= 0 && nextNum <= 100000 && time[nextNum] == 0) {
                    // 가능한 범위 내에서 처음 방문하는 노드이면 Queue에 해당 인덱스 넣음
                    // 소요시간은 그 전 탐색한 노드의 소요시간  + 1
                    queue.offer(nextNum);
                    time[nextNum] = time[num] + 1;
                }
            }
        }

    }

}

---

문제 풀이

수빈이가 1초에 이동할 수 있는 방법이
1. X-1로 이동
2. X+1로 이동
3. 2×X의 위치로 이동
위 세 가지이므로 시작 정점 n에서부터 n-1, n+1, 2×n의 위치에 있는 정점은 소요시간이 1초이다.
bfs를 이용해 소요시간이 x초인 정점의 탐색하지 않은 인접 정점에 도달하는데 걸리는 시간은 x+1초가 된다.
처음으로 k에 인접한 정점을 발견하면 탐색을 종료하고 소요시간을 출력하면 된다.

---

Review

그래프를 이용하는 문제에 아직 익숙하지 않아서 문제 풀이 방법이 쉽게 떠오르지 않았다. dfs와 bfs에 대한 개념이 아직 부족하다고 생각한다. 한번 개념 정리를 작성해봐야겠다.