13549번

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

13549번: 숨바꼭질 3

이번 문제는 저번에 BFS로 풀은 숨바꼭질 문제와 같은 문제이다. 차이점이라면 시간의 계산 정도이다.

하지만 이 차이점이 문제 풀이에 큰 영향을 준다. 이 문제를 풀면서 몇몇 사람들은 대입되는 인접리스트의 순서에 따라서 정답이 맞고, 틀리는 경우가 발생했다고 한다. 그것에 대한 증명을 하는 것은 어려운 일이다.

그렇지만 문제를 풀때 BFS로 적용 해야 할지 다익스트라로 해야 할지 판단하는 것은 이 계산의 차이, 가중치의 유무이다.

BFS의 경우는 전제가 모든 간선의 가중치가 같아야한다는 것이고, 다익스트라는 가중치의 차이가 간선마다 있다는 것이다.

그래서 이번에는 다익스트라를 이용해서 이번 문제를 풀어보려고 한다.

 

다익스트라는 우선순위 큐와 BFS를 합친 알고리즘이라고 생각한다.

그래서 이 문제에서는 1, -1, *2로 이동하는 경우로 나뉜다. 그 중에서 *2의 경우는 시간계산을 0으로 한다.

1,-1은 +1로 계산한다.

나머지는 다익스트라의 기본 로직인 현재 계산한 로직의 값이 저장된 가중치 값보다 크면 넘어가고, 현재의 가중치에 다음 인접 노드로 가는 가중치를 계산해서 인접 노드에 이전에 계산한 가중치와 비교해서 작으면 갱신하는 방식이다.

 

처음에는 다익스트라의 원리와 로직이 많이 헷갈렸었다. 공부와 질문을 통해서 이해한 다익스트라는 같은 노드를 여러번 반복하는 줄 알았는데, 그것이 아니라 우선순위 큐에 같은 노드가 여러번 들어갈 수 있다는 것이다.

 

정답 코드는 아래와 같다.

package backjoon.b13549;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.io.*;
import java.util.StringTokenizer;

public class b13549 {
    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());
        Graph g = new Graph(N,K);
        g.dijkstra(N,K);
        System.out.println(g.distance[K]);
    }
}
class Graph{
    int N;
    int M;
    int[] distance;
    PriorityQueue<Node> queue;
    public Graph(int N, int M){
        this.N=N;
        this.M=M;
        queue = new PriorityQueue<>();
        distance = new int[100001];
    }
    public void dijkstra(int R, int E){
        Arrays.fill(distance,Integer.MAX_VALUE);
        queue.add(new Node(0,R));
        distance[R]=0;
        while (!queue.isEmpty()){
            Node poll = queue.poll();
            if(poll.cnt>distance[poll.x])continue;
            if(poll.x==E){
                return;
            }
            if(poll.x+1<=100000){
                if(poll.cnt<distance[poll.x+1]){
                        queue.add(new Node(poll.cnt+1, poll.x+1));
                        distance[poll.x+1]=distance[poll.x]+1;
                }
            }
            if(poll.x-1>=0){
                if(poll.cnt<distance[poll.x-1]){
                        queue.add(new Node(poll.cnt+1,poll.x-1));
                        distance[poll.x-1] = distance[poll.x]+1;
                }
            }
            if(poll.x*2<=100000){
                if(poll.cnt<distance[poll.x*2]){
                        queue.add(new Node(poll.cnt, poll.x*2));
                        distance[poll.x*2]=distance[poll.x];
                }
            }
        }
    }
}
class Node implements Comparable<Node>{
    int cnt;
    int x;

    public Node(int cnt, int x) {
        this.cnt = cnt;
        this.x = x;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(cnt,o.cnt);
    }
}