[알고리즘] 백준 13549 숨바꼭질 3 - JAVA

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제설명

5 -> 17 좌표로 이동하기 위한 최소의 cost를 구하는 문제다. 

 

좌표는 현재 기준에서 +1, -1, *2 위치로 이동할 수 있다.

 

+1과 -1 위치로 이동할 때의 cost는 1이고, *2 위치로 이동할 때의 cost는 0이다.

 

풀이과정

가중치가 다른 그래프 문제기 때문에 bfs를 그냥 돌리면 방문 순서에 따라 cost가 달라진다.

 

최소 비용을 올바르게 구하기 위해서는 힙을 사용해야 한다. 

 

나는 우선순위 큐를 통해 문제를 풀었지만 다익스트라로 풀 수도 있다.

 

우선순위큐에서 cost값을 기준으로 poll하기 위해 comparable을 사용했다.

 

다익스트라를 통해 풀지 않으면 시간이 터지지 않을까 의문이 생길 수 있는데 그렇지는 않다.

 

큐에 들어있는게 엄청 많아지기는 하겠지만 이것들이 다 빠지기 전에 정답이 나와서 반환되기때문

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

    static int N;
    static int K;
    static int[] map;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[100001];
        visited = new boolean[100001];
        System.out.println(search());
    }

    static int search() {

        if (N == K) // 시작위치가 목적지면 0반환
            return 0;

        PriorityQueue<Location> pq = new PriorityQueue<>();
        pq.add(new Location(N, 0));
        visited[N] = true;

        while (!pq.isEmpty()) {
            Location current = pq.poll(); 
            visited[current.x] = true; // 이 때 방문체크를 해야 순서 의존도가 생기지않음. 

            if (isFinalLocation((current.x))) {
                return current.value;
            }

            if (current.x * 2 < 100001 && !visited[current.x * 2]) {
                pq.add(new Location(current.x * 2, current.value));
            }

            // 왼
            if (current.x - 1 >= 0 && !visited[current.x - 1]) {
                pq.add(new Location(current.x - 1, current.value + 1));
            }
            // 오
            if (current.x + 1 < 100001 && !visited[current.x + 1]) {
                pq.add(new Location(current.x + 1, current.value + 1));
            }
        }
        return -1;
    }

    static boolean isFinalLocation(int x) {
        if (x == K) {
            return true;
        }
        return false;
    }

    static class Location implements Comparable<Location>{
        int x;
        int value;

        public Location(int x, int value) {
            this.x = x;
            this.value = value;
        }

        @Override
        public int compareTo(Location o) {
            return this.value - o.value;
        }
    }
}