[백준 -자바] 13549번 : 숨바꼭질3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

"숨바꼭질" 문제들이 BFS로 풀이가 되는게 많아서 BFS로만 접근했다가 도저히 정답이 나오질 않았다...

 

그래서 참고 자료를 찾아보니

 

원래 이 문제는 단순한 BFS를 요구하는 문제가 아니다. 왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐이다. 왜 하필 이 순서로 하면 항상 정답이 나오는가를 증명하는 건 매우 복잡한 일이다.

 

이 문제를 보다 일반화된 경우 (가중치가 0인 간선이 있는 경우)에 대해 해결하려면, 즉, 이 문제의 의도대로 풀려면 다음과 같은 방법들을 사용할 수 있다.

• 다익스트라 알고리즘
• 0-1 BFS: 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
• * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

 

즉, 이 문제는 간선의 비용이 다르기 때문에 특정 노드(목표치)까지 최단거리를 찾기 위해서는 BFS가 아닌 다익스트라 알고리즘을 사용해야한다.

 

다익스트라 알고리즘은 큐에 새로운 노드를 넣을 때 마다 노드들을 비용기준 오름차순으로 정렬하고, 가장 비용이 적은 노드를 꺼내며 최단거리를 갱신한다.

 

import java.util.*;

class Point implements Comparable<Point> {

    int idx;
    int time;

    public Point(int index, int time) {
        this.idx = index;
        this.time = time;
    }

    @Override
    public int compareTo(Point o) {
        return Integer.compare(this.time, o.time);
    }
}

public class _13549_숨바꼭질3 {

    public static final int INF = (int) 1e9;
    public static int n, k;
    public static int[] d = new int[100_001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        Arrays.fill(d, INF);

        PriorityQueue<Point> pq = new PriorityQueue<>();
        d[n] = 0;
        pq.offer(new Point(n, 0));

        while (!pq.isEmpty()) {
            Point now = pq.poll();
            int idx = now.idx;
            int time = now.time;

            if (idx * 2 <= 100_000 && d[idx * 2] > time) {
                d[idx * 2] = time;
                pq.offer(new Point(idx * 2, time));
            }
            if (idx - 1 >= 0 && d[idx - 1] > time + 1) {
                d[idx - 1] = time + 1;
                pq.offer(new Point(idx - 1, time + 1));
            }
            if (idx + 1 <= 100_000 && d[idx + 1] > time + 1) {
                d[idx + 1] = time + 1;
                pq.offer(new Point(idx + 1, time + 1));
            }


        }

        System.out.println(d[k]);
    }
}

 

 

---

참고

https://www.acmicpc.net/board/view/38887#comment-69010

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문