[백준] 13549번 : 숨바꼭질 3

13549번: 숨바꼭질 3

# 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

# 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

# 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

# 예제 입력

5 17

# 예제 출력

2

---

[다익스트라 알고리즘]

1. 0부터 100,000까지의 배열 distance[]을 모두 INF로 초기화한다.

 

2. 다익스트라 함수를 실행하고 시작 정점은 n이다.

 

3. distance[n] = 0으로 설정하고 우선순위 큐에 n번 정점과 distance[n]을 enqueue한다.

 

4. 우선순위 큐에서 원소를 꺼내 정점과 가중치를 확인하고 최소 값을 갱신할 필요가 있으면 갱신한다.

 

5. 1초 후에 X-1, X+1칸으로 이동할 수 있고, 0초 후에 X*2칸으로 이동할 수 있음에 주의한다.(단, 0<= a <= 100,000)

 

6. 우선순위 큐에 1초 후에 갈 수 있는 곳과 그 때의 가중치 + 1을 해서 넣고, 0초 후에 갈 수 있는 곳과 가중치는 그대로 넣는다.

 

7. 현재 방문하고 있는 정점이 k이면 루프를 빠져나와 함수를 종료한다.

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int target, dist;
        public Edge(int t, int d){
            target = t;
            dist = d;
        }
        @Override
        public int compareTo(Edge o) {
            return dist-o.dist;
        }
    }
    
    static final int MAX = 100000;
    static final int INF = 1000000000;
    
    static int n,k;
    
    static int[] distance = new int[MAX+1];
    
    static Queue<Edge> Q = new PriorityQueue<>();
    
    static int[] X = {-1, 1, 0};

    static int Dijkstra(int start){
        distance[start] = 0;
        Q.add(new Edge(start, 0));

        while(!Q.isEmpty()){

            Edge edge = Q.poll();
            int current = edge.target;
            int dist = edge.dist;

            if(current == k) break;
            if(distance[current] < dist) continue;

            X[2] = current; //current + current = current * 2이다.
            for(int i=0; i<3; i++){
                int next = current + X[i];
                int nextDistance = (i<2)? dist+1: dist;

                if(next >= 0 && next <= MAX && distance[next] > nextDistance){
                     distance[next] = nextDistance;
                     Q.add(new Edge(next, nextDistance));
                }
            }
        }
        //큐를 비워주는 것이 보다 더 안정적이지만 테스트 케이스가 1개이므로 쓰지 않았다.
        //Q.clear();
        return distance[k];
    }

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

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=0; i<=MAX; i++)
            distance[i] = INF;

        System.out.println(Dijkstra(n));
    }
}