이것저것 개발 블로그

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

풀이)

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main_BJ_13549_숨바꼭질3 {
    static int MAX = 100000;
    static boolean[] visited = new boolean[MAX+1];
    static class location{
        int x;
        int cnt;

        public location(int x, int cnt){
            this.x = x;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        PriorityQueue<location> pq = new PriorityQueue<>(new Comparator<location>() {
            @Override
            public int compare(location o1, location o2) {
                return o1.cnt - o2.cnt;
            }
        });
        visited[n] = true;
        pq.offer(new location(n, 0));
        int min = Integer.MAX_VALUE;

        while(!pq.isEmpty()){
            location cur = pq.poll();
            visited[cur.x] = true;

            if(cur.x == m){
                min = Math.min(min, cur.cnt);
            }

            if(cur.x-1 >= 0 && !visited[cur.x-1])
                pq.offer(new location(cur.x-1, cur.cnt+1));

            if(cur.x+1 <= MAX && !visited[cur.x+1])
                pq.offer(new location(cur.x + 1, cur.cnt + 1));

            if(cur.x * 2 <= MAX && !visited[cur.x * 2])
                pq.offer(new location(2 * cur.x, cur.cnt));

        }//while

        System.out.println(min);
    }//main
}

이 문제는 Priority Queue + BFS로 풀 수 있는 문제였다!

처음에는 pq에 comparator로 Math.abs(현재 좌표 - 목표 좌표)로 해서 가까운 순으로 체크하려 했는데, 이러면 안됐고,,,

대신 pq에 시간 기준으로 가장 적은 순으로 넣으면 된다.

대신 pq에 삽입할 때 범위를 체크한 후 삽입해야한다.

또한, bfs로 visited를 체크할 때 pq에서 뽑았을 때 해야한다는 주의점이 있다. (pq에 넣을 때 순서 의존도가 생기기 때문에..)

pq, bfs까지도 잡았는데 visited에서 잘 생각하지 못한 부분이 아쉽다.