[백준] 13549번 - 숨바꼭질 3 (Gold 5)

문제 링크

백준 13549번 - 숨바꼭질 3 (Gold 5)

문제 설명

좌표 N에서 K까지 이동하고자 한다.($1 \leq N, K \leq 100000$) 좌표 X 이동할 수 있는 방법은 두 가지이다.

1. X-1 또는 X+1로 걸어서 1초 동안 이동
2. 2*X로 순간 이동

이 때 N에서 K까지 이동하는데 드는 최소 시간을 구하면 된다.

정답 코드 및 설명

풀이 1 : 일반적인 BFS 이용

평범한 BFS를 이용하는데, 순간 이동은 이동 시간이 없음에 주의한다.
순간 이동을 여러번 취하는 경우 더 나중에 찾은 경로이지만 실제 소요 시간은 더 짧은 경로도 나올 수 있다.
따라서 모든 경로를 전부 탐색한 후에 그 중에서 가장 짧은 시간을 리턴해야 한다.

import java.io.*;
import java.util.*;

public class Main {

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

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

        bw.write(time(n, k) + "");
        bw.close();
    }

    static int time(int n, int k) {
        int[] time = new int[100001];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        time[n] = 1;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            int[] next = new int[] { curr - 1, curr + 1, 2 * curr };
            for (int i = 0; i < 3; i++) {
                if (next[i] < 0 || next[i] > 100000)
                    continue;
                if (next[i] >= 0 && (time[next[i]] == 0 || time[next[i]] > time[curr])) {
                    queue.add(next[i]);
                    time[next[i]] = time[curr];
                    // 순간 이동하지 않는 경우
                    if (i != 2)
                        time[next[i]]++;
                }
            }
        }
        return time[k] - 1;
    }
}

풀이 2 : 0-1 BFS 이용

BFS의 변형 버전이다. 일반적인 BFS는 큐를 이용하지만, 0-1 BFS에서는 덱을 이용한다.
가중치가 0인 경우에는 덱의 앞쪽에 추가하고, 가중치가 1인 경우에는 덱의 뒤쪽에 추가하는 형태이다.
이렇게 하면 가중치가 0인 경우를 먼저 탐색하게 되므로, 무조건 소요 시간이 짧은 경로부터 탐색하게 된다.

import java.io.*;
import java.util.*;

public class Main {

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

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

        bw.write(time(n, k) + "");
        bw.close();
    }

    static int time(int n, int k) {
        int[] time = new int[100001];
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(n);
        time[n] = 1;
        while (!deque.isEmpty()) {
            int curr = deque.pollFirst();
            if (curr * 2 <= 100000 && (time[curr * 2] == 0 || time[curr * 2] > time[curr])) {
                deque.addFirst(curr * 2);
                time[curr * 2] = time[curr];
            }
            int[] next = new int[] { curr - 1, curr + 1 };
            for (int i = 0; i < 2; i++) {
                if (next[i] < 0 || next[i] > 100000)
                    continue;
                if (next[i] >= 0 && (time[next[i]] == 0 || time[next[i]] > time[curr] + 1)) {
                    deque.addLast(next[i]);
                    time[next[i]] = time[curr] + 1;
                }
            }
            if (time[k] != 0)
                return time[k] - 1;
        }
        return -1;
    }
}