1697 - 숨바꼭질

BFS를 이용해, 시작 좌표부터 최종 좌표까지 도달하기위한 최소 시간을 구하는 문제이다.

시작 좌표로부터 그 다음 좌표로 이동하는 방법이 총 3가지 이다.

시작 좌표를 C라고 했을 때, (C - 1, C + 1, C * 2).

따라서 시작 정점으로부터 3개의 자식 노드를 가지는 트리 형식이라고 생각하고 풀이했다.

 

틀렸던 점들은 주석으로 표시해두는 방식을 채택했다.

각 2차원 배열들의 역할은

map -> 방문 여부

time -> 해당 좌표에 도달하기 위한 최소 시간

이다.

 

첫 번째 실수는 사소한 실수였고, 두 번째 실수가 엣지 케이스에대한 실수였다.

시작 지점이 0이 아닌 수이고, 도착 지점이 0이라면

항상 -1을 이용해 도착 지점에 도달해야 한다. 하지만 양수 범위만 생각한 나머지 cur - 1 > 0 과 같이 조건문을 작성해 틀리게 되었다.

 

추가적으로 MAX가 200000인 이유는, N 범위가 0 <= N <= 100000이므로 * 2가 실행되었을 때 최대로 도달 할 수 있는 좌표라고 생각하게되어 200000으로 지정했다.

package backjoon;
import java.util.*;
import java.io.*;

public class P_1697 {
    static int MAX = 200000;
    public static void bfs(int N, int[] map, int[] time){
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        map[N] = 1; // 처음에 방문한 N을 방문 처리를 해주지 않음.
        while (!q.isEmpty()){
            int cur = q.poll();
            if (cur + 1 < MAX)
            {
                if (map[cur + 1] == 0) {
                    q.add(cur + 1);
                    map[cur + 1] = 1;
                    time[cur + 1] = time[cur] + 1;
                }
            }
            if (cur - 1 < MAX && cur - 1 >= 0) // cur - 1이 0이 될 때 까지 돌 필요가 있음.
            {
                if (map[cur - 1] == 0) {
                    q.add(cur - 1);
                    map[cur - 1] = 1;
                    time[cur - 1] = time[cur] + 1;
                }
            }
            if (cur * 2 < MAX)
            {
                if (map[cur * 2] == 0) {
                    q.add(cur * 2);
                    map[cur * 2] = 1;
                    time[cur * 2] = time[cur] + 1;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = inputs[0];
        int K = inputs[1];
        int[] map = new int[MAX];
        int[] time = new int[MAX];
        bfs(N, map, time);
        System.out.println(time[K]);
    }
}