백준 13549 - 숨바꼭질3

문제

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

리뷰

이 문제를 예전에 0-1 BFS로 풀이했던 기억이 있는데 오랜만에 다시 보니
틀림으로 재채점 되어 있어 다시 풀이하였다.

다익스트라를 이용하여 -1, +1, *2 각각의 세 방향 이동시 유효한
인덱스인지 검사하고 진행이 가능할 경우 비용 기준 최소힙에 간선들을 누적하며
각 정점까지의 최소 비용을 담는 dist 배열을 갱신하여 dist[K]
(=K까지의 최소 비용)을 구하는 방식으로 문제를 풀이하였다.

한편, 우선순위큐에 정점 번호와 비용을 함께 표현하기 위해 Node라는
클래스를 별도로 정의하였다.

예전에 BFS와 Deque를 이용하여 이 문제를 풀이했던 기억이 있는데
찾아보니 최소 비용을 도출해야 하기 때문에, 도착 지점을 마주한다고
탐색을 중단할 것이 아니라 큐를 모두 비울때까지 탐색을 지속해야 했다.
이 부분은 아래 좋은 글을 있기에 첨부한다.

참고 : 0-1 BFS 이용 풀이
https://velog.io/@silver_star/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-BFS

코드

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

import static java.lang.Integer.parseInt;

public class Main{
    static int N, K;

    static final int MAX=100_001;
    static int[] dist=new int[MAX];

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

        N=parseInt(st.nextToken());
        K=parseInt(st.nextToken());
        Arrays.fill(dist, Integer.MAX_VALUE);

        dijkstra(N);

        System.out.println(dist[K]);
        br.close();
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq=new PriorityQueue<>(Comparator.comparingInt(n->n.level));
        dist[start]=0;
        pq.offer(new Node(start, dist[start]));

        while(!pq.isEmpty()){
            Node current=pq.poll();

            if(2*current.number<MAX && dist[2*current.number]>current.level){
                dist[2*current.number]=current.level;
                pq.offer(new Node(2*current.number, dist[2*current.number]));
            }

            if(current.number+1<MAX && dist[current.number+1]>current.level+1){
                dist[current.number+1]=current.level+1;
                pq.offer(new Node(current.number+1, dist[current.number+1]));
            }

            if(current.number-1>=0 && dist[current.number-1]>current.level+1){
                dist[current.number-1]=current.level+1;
                pq.offer(new Node(current.number-1, dist[current.number-1]));
            }
        }
    }

    static class Node{
        int number, level;

        public Node(int number, int level) {
            this.number = number;
            this.level = level;
        }
    }
}

결과