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

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

13549번: 숨바꼭질 3

풀이

사용한 알고리즘 : 다익스트라

 

풀이전략

 

이동할 때마다 드는 비용이 순간이동시에 0, 좌우 이동시에 1이 든다.

이동할 때 드는 비용이 모두 같은 경우에는 너비우선탐색(BFS)를 사용하겠지만

해당 문제에서는 그렇지 않기 때문에 다익스트라를 사용하여 문제를 풀이한다.

 

다익스트라에서는 우선순위 큐를 사용하는데,

이 문제에서는 가장 적은 비용으로 특정 위치에 도달하는 것이 목표이므로 비용을 기준으로 큐를 정렬시킨다.

 

단, 어떤 위치에서 어떤 비용이 드는지도 알아야 하기에 이를 묶어줄 수 있는 클래스를 정의하였다.

Compable 인터페이스를 구현하여 우선순위 큐 내부에서 비용을 기준으로 오름차순 정렬하도록 하였다.

 

우리가 이동하는 경우의 수는 총 3가지로,

순간 이동하여 원래 위치에서 X2 하는 경우,

전진하여 원래 위치에서 +1하는 경우,

후진하여 원래 위치에서 -1하는 경우이다.

 

따라서 주어진 시작점으로부터 위의 세가지 경우를 각각 탐색하고,

해당 위치가 주어진 범위인 0<=x<=100,000을 넘지 않으면서  이전에 탐색하지 않았을 경우

우선순위 큐에 삽입하는 과정을 반복한다.

 

그러면 비용에 따라 우선순위 큐를 정렬했으므로

비용이 0인 것부터 1, 2, 3, ..., n 순서로 탐색을 시작할 것이다.

 

탐색 도중 우리가 목표로 했었던 K에 도달한 경우,

해당 위치에서의 비용을 출력하면 정답을 도출할 수 있다.

 

제출코드

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

public class Main {
    static int N,K;
    static int MAX_COUNT=100001;
    static boolean visited[]=new boolean[MAX_COUNT];

    static class Pos implements Comparable<Pos>{
        int index;
        int cost;

        public int getIndex(){
            return this.index;
        }

        public int getCost(){
            return this.cost;
        }

        public Pos(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Pos o) {
            if(this.cost<o.cost) return -1;
            else return 1;
        }
    }
    static int dijkstra(int start){
        PriorityQueue<Pos> q = new PriorityQueue<>();
        q.offer(new Pos(start,0));
        int result=0;

        while(!q.isEmpty()){
            Pos temp = q.poll();
            int now = temp.getIndex();
            visited[now]=true;

            if(now==K){
                result=temp.getCost();
                break;
            }

            if(now*2<MAX_COUNT && !visited[now*2]){
                int cost=temp.getCost();
                q.offer(new Pos(now*2,cost));
            }
            if(now-1>=0 && now-1<MAX_COUNT && !visited[now-1]){
                int cost=temp.getCost()+1;
                q.offer(new Pos(now-1,cost));
            }
            if(now+1<MAX_COUNT && !visited[now+1]){
                int cost=temp.getCost()+1;
                q.offer(new Pos(now+1,cost));
            }
        }
        return result;
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        bw.write(dijkstra(N)+"\n");
        bw.flush();
        bw.close();
    }
}