[자바]백준 13549번 숨바꼭질3 [그래프-다익스트라][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

문제

수빈이는 동생과 숨바꼭질을 하고 있다.
수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 
수빈이는 걷거나 순간이동을 할 수 있다.
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

 

예제 출력 1

2

힌트

 

수빈이가 5-10-9-18-17 순으로 가면 2초 만에 동생을 찾을 수 있다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 0-1 너비 우선 탐색 (가중치가 0과 1만 존재하는 그래프에서 최단 경로를 찾는 알고리즘)

---

문제 설명

문제 자체는 어렵지 않게 해석할 수 있다.
간단히 설명하면, 수빈이가 동생의 위치까지 이동하는 가장 빠른 시간을 찾아내는 것이다.

여기서 규칙이 추가되는데 수빈이 위치에서 곱하기 2를 하면 시간이 0초가 소요되고, +1, -1을 하면 1초가 소요된다는 것이다.

해설1 (생략 가능)

해당 문제는 우선 백준에서 데이크스트라(다익스트라, dikstra)와 0-1 너비 우선 탐색으로 분류되어있다.

0-1 너비 우선 탐색은 0과 1만 존재하는 그래프에서 효율적으로 해결해 나갈 수 있는 알고리즘이다.

처음에는 이게 왜 너비 우선 탐색이지 싶었지만, 0-1 너비 우선 탐색기준으로는 너비 우선 탐색이구나 싶었다.

 

왜 이해가 안 되었었냐면, 너비 우선 탐색은 깊이가 같은 노드들을 먼저 탐색하는 것이다.

 

하지만 해당 문제는 아래와 같이 깊이 우선 탐색이 아닌가 싶었다. (0, 1은 시간을 나타낸다.)

하지만 0-1 너비 우선 탐색은 아래와 같이 시간 자체를 깊이로 생각하고 같은 시간(깊이)을 먼저 탐색하는 너비 탐색 방식인 것이다.

해설2

우선 해당 문제는 아래와 같이 2가지 준비물이 필요하다.

• PriorityQueue
• boolean[] (방문 배열)

PriorityQueue는 0-1 너비 우선 탐색을 위한 도구로 이 외에 Deque, LinkedList로도 구현 가능하다.

boolean 배열은 같은 거리를 두 번 이상 탐색하지 않기 위해 필요하다.
예를 들어서 수빈이가 5라는 위치에 있다고 가정하자 여기서 +1, -1, x2에는 6, 4, 10이 있다.
그렇다면 그다음에 해당 6위치로 이동하고 6에서 그다음 노드를 계산하면 7, 5, 12가 나온다.
만약 5를 방문 배열에 기록을 남기지 않았다면,  5 -> 6 -> 5 -> 6... 를 무한히 반복하다 stackoverflow 에러가 발생하게 되기 때문에 반드시 필요하다. (boolean 배열 외에 다른 방식으로 방문을 알 수 있게 할 수 있다면, 편한 방법을 사용하면 된다.)

준비된 후에는 다음과 같은 방식으로 코드를 작성하면 된다.

 

1. 현재 위치까지 오는 시간을 카운트해 주고, 방문 기록한다. 

2. 이동 위치와 시간을 PriorityQueue에 넣어준다. 

• 여기서 주의할 점은 x2한 노드(위치, 시간)를 앞에 배치하고 +1, -1 이동한 노드는 순서대로 배치한다.
• PriorityQueue를 사용하면 시간 오름차순으로 설정해 준다.
• Deque, LinkedList를 사용할 경우에는 x2한 노드는 앞에 배치, +1, -1 이동한 노드는 뒤에 배치해준다.

 

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.PriorityQueue;

public class Main {
    static int N; // 수빈이 위치
    static int K; // 동생 위치
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
        pq.offer(new int[]{N, 0});
        boolean[] visited = new boolean[100_001];

        int count = 0;
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int nPosition = now[0];
            count = now[1];

            if (nPosition == K) {
                break;
            }

            visited[nPosition] = true;
            if (nPosition * 2 <= 100_000 && !visited[nPosition * 2]) {
                pq.offer(new int[] {nPosition * 2, count});
            }

            if (nPosition < K && nPosition + 1 <= 100_000 && !visited[nPosition + 1]) {
                pq.offer(new int[] {nPosition + 1, count + 1});
            }

            if (nPosition - 1 >= 0  && !visited[nPosition - 1]) {
                pq.offer(new int[] {nPosition - 1, count + 1});
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}