13549 - 숨바꼭질 3

이전에 있었던 숨바꼭질 문제와 같은 문제인데, 가중치가 모든 경우마다 같은것이 아닌 0 - 1 총 두 가지의 가중치를 가진 문제이다.

 

같은 가중치를 가지고 있을 경우, BFS를 실행하면 최선의 답을 구할 수 있지만, 다른 가중치를 가지고 있을 경우 BFS를 돌린다고해서 최선의 답이 아닐 수 있다. (방문한 노드가 이전에 BFS를 돌렸던 노드보다 가중치가 클 수 있다.)

그래서, 보통 Queue를 2개 사용하여 현재 큐 - 다음 큐 와 같은 형식으로 구현해 문제를 풀이하게 된다.

하지만, Deque 자료구조를 이용하여 addFirst, addLast 메소드들을 이용하면 Deque 하나로 문제를 풀이 할 수 있게 된다.

가중치가 더 작은 쪽이 *2 연산을 하는 쪽이므로(0초 소요), 큐의 앞쪽에 삽입하여 먼저 처리 될 수 있게 하고, 나머지 경우들은 큐의 뒤쪽에 섭입하여 앞쪽에서 가중치가 더 작은 경우들이 먼저 다 실행되고 난 후 실행되게 구현하였다.

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

public class Main {
    static int MAX = 200000;
    public static void bfs(int N, boolean[] map, int[] time, int[] from) {
        Deque<Integer> dq = new LinkedList<>();
        dq.add(N);
        map[N] = true;
        while (!dq.isEmpty()) {
            int current = dq.poll();
            if (current * 2 < MAX) {
                if (!map[current * 2]) {
                    dq.addFirst(current * 2);
                    time[current * 2] = time[current];
                    from[current * 2] = current;
                    map[current * 2] = true;
                }
            }
            if (current - 1 >= 0) {
                if (!map[current - 1]) {
                    dq.addLast(current - 1);
                    time[current - 1] = time[current] + 1;
                    from[current - 1] = current;
                    map[current - 1] = true;
                }
            }
            if (current + 1 < MAX) {
                if (!map[current + 1]) {
                    dq.addLast(current + 1);
                    time[current + 1] = time[current] + 1;
                    from[current + 1] = current;
                    map[current + 1] = true;
                }
            }
        }
    }

    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[] time = new int[MAX];
        boolean[] map = new boolean[MAX];
        int[] from = new int[MAX];
        bfs(N, map, time, from);
        System.out.println(time[K]);
    }
}

주의해야 할 부분은, 가중치가 같을 경우(-1, +1 모두 가중치가 1로 동일함) 두 경우 중 더 최선인 경우로 선택해야 한다. 이외에는 동일함.