백준 알고리즘 13549번: 숨바꼭질 3

문제 파악

---

문제 조건

• 수빈이의 위치 N(0 <= N <= 100,000)
• 동생의 위치 K(0 <= K <= 100,000)
• 수빈이의 위치가 X일 때 걸으면 1초 후에 X-1 또는 X+1 로 이동
• 순간이동을 하면, 0초 후에 2*X 로 이동

 

문제 내용

수빈이가 동생을 찾는 가장 빠른 시간을 출력하는 문제이다

 

 

풀이

---

생각했던 내용

이 문제는 기존 문제인 숨바꼭질(https://www.acmicpc.net/problem/1697) 과는 조금 다른 문제이다.

기존 문제는 가중치가 모두 같은(걷는 경우와 순간이동을 하는 경우) 문제이지만, 이 문제는 가중치가 서로 다르다.

걷는 경우는 1초 후에 이동하고, 순간이동을 하면 0초 후에 이동을 하기 때문에 순간이동을 하는 경우 우선순위를 두고 최대한 순간이동을 많이 사용하도록 문제를 풀이해야 한다

 

풀이한 내용

내가 풀이했던 방법은 0-1 BFS 라는 알고리즘으로 풀이했다. (https://nicotina04.tistory.com/168)

해당 방법을 사용하면, 모든 경로를 탐색하지 않고 우선순위가 높은(비용이 적게 드는) 경로를 먼저 택하여 업데이트해주기 때문에 더 빠르게 문제를 풀이할 수 있다.

 

기존 BFS 에서는 Queue를 사용하지만, 0-1 BFS 에서는 Deque 를 사용한다.

그 이유는, 우선순위가 높은(비용이 적게 드는) 경로라면 먼저 해당 경로를 탐색하고 우선순위가 낮은(비용이 많이 드는) 경로는 최대한 나중에 탐색하도록 해야 하고,

이를 구현하려면 Deque 로 우선순위가 높은것은 addFirst 메서드를 사용하여 덱의 앞부분에 추가하여 해당 경로를 먼저 탐색하도록(높은 우선순위를 갖도록) 구현할 수 있으며 우선순위가 낮다면 addLast 메서드를 사용하여 후순위로 미루어서 탐색하도록 할 수 있다.

 

문제 풀이는 어렵지 않을 것이다. 최대 100,000 까지의 점들을 탐색할 수 있으므로 우리는 해당 위치에 갈 수 있는 최소 비용을 기록하기 위해 int[] weight = new int[100001]  로 비용을 기록할 것이다.

시작 위치는 비용이 없으므로 weight[N] = 0 으로 초기화 해준다.

 

그 후, 순간이동을 하는 경우부터 시작하여 한칸 뒤로 걷는 경우, 한칸 다음으로 걷는 경우의 총 3가지 경우를 생각하며 비용 배열을 업데이트해 나가면 될 것이다.

 

마지막으로, 수빈이의 위치가 동생의 위치보다 앞에 있다면 동생의 위치로 가는 유일한 방법은 1칸씩 뒤로 가는 것 밖에 없다.

(K < N 인 경우)

 

따라서 이 경우에는 단지 N-K 를 출력해줌으로써 불필요한 계산을 하지 않도록 할 수 있다.

 

또한 이 문제는 0-1 BFS 를 통하여 풀었지만, 다익스트라를 통해서 문제를 풀이할 수 있으니 공부해보면 좋을 것 같다

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Arrays.fill(weight, 100001);
        weight[N] = 0;

        if (K < N) {
            System.out.println(N - K);
            return;
        }
        bfs(N, K);
    }

    static int[] weight = new int[100001];

    public static void bfs(int N, int K) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(N);

        while (!deque.isEmpty()) {
            int current = deque.pollFirst();

            if (current == K) {
                System.out.println(weight[current]);
                return;
            }

            int jump = current * 2;
            if (isValid(jump) && weight[jump] > weight[current]) {
                deque.addFirst(jump);
                weight[jump] = weight[current];
            }

            int walkBack = current - 1;
            if (isValid(walkBack) && weight[walkBack] > weight[current] + 1) {
                deque.addLast(walkBack);
                weight[walkBack] = weight[current] + 1;
            }

            int walkFront = current + 1;
            if (isValid(walkFront) && weight[walkFront] > weight[current] + 1) {
                deque.addLast(walkFront);
                weight[walkFront] = weight[current] + 1;
            }
        }
    }

    public static boolean isValid(int current) {
        return current >= 0 && current <= 100000;
    }
}

 

 

Source Code on GitHub

---