다익스트라 (boj 12851 숨바꼭질2)

문제 : https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

기존의 숨바꼭질 문제에서 최단경로의 갯수까지 구해야 한다.

 

1. 목적지에 도달하면 함수를 종료하는 것이 아닌 계속 탐색을 이어나가도록 함수를 구성했다.

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

            if(cur.idx==K && cur.w==dist[K]){ // 목표지점에 도달한 경우
                count+=1;
            }
            
 ...
 
 }

 

2. 또한 모든 가능한 경로를 탐색하기 위해 기존 다익스트라 코드를 수정했다.

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

            // 기존 다익스트라는 < 이지만, 모든 경우를 보기 위해서 <=
            if(cur.idx-1 >= 0 && cur.w + 1 <= dist[cur.idx-1]){
                dist[cur.idx-1] = cur.w + 1;
                pq.offer(new Node(cur.idx-1,cur.w+1));
            }
            if(cur.idx+1 <= 100000 && cur.w + 1 <= dist[cur.idx+1]){
                dist[cur.idx+1] = cur.w + 1;
                pq.offer(new Node(cur.idx+1,cur.w+1));
            }
            if(cur.idx*2 <= 100000 && cur.w + 1 <= dist[cur.idx*2]){
                dist[cur.idx*2] = cur.w + 1;
                pq.offer(new Node(cur.idx*2,cur.w+1));
            }

        }

기존 다익스트라 코드에선 cur.w + 1 < dist[cur.idx - 1] 과 같이 < 부등호를 사용했다.

하지만 모든 가능한 경우를 탐색해야 하기 때문에 <= 부등호를 사용해야 했다.

 

3. 불필요한 탐색을 중지하여 시간을 줄일 수 있었다.

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

           ...
           
            if(cur.w > dist[K]){ // 목적지 보다 먼 경우를 탐색하기 시작하면 함수를 종료해도 됨.
                return;
            }

            ...

        }

 

344ms에서 228ms로

 

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

public class Main {

    // BOJ 12851
    // 다익스트라

    static final int INF = (int)1e9;
    static int N,K;
    static int[] dist;
    static PriorityQueue<Node> pq;
    static int count;

    static void solve(){

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

            if(cur.idx==K && cur.w==dist[K]){ // 목표지점에 도달한 경우
                count+=1;
            }

            if(dist[cur.idx] < cur.w) continue; // 방문체크

            if(cur.w > dist[K]){ // 목적지 보다 먼 경우를 탐색하기 시작하면 함수를 종료해도 됨.
                return;
            }

            // 기존 다익스트라는 < 이지만, 모든 경우를 보기 위해서 <=
            if(cur.idx-1 >= 0 && cur.w + 1 <= dist[cur.idx-1]){
                dist[cur.idx-1] = cur.w + 1;
                pq.offer(new Node(cur.idx-1,cur.w+1));
            }
            if(cur.idx+1 <= 100000 && cur.w + 1 <= dist[cur.idx+1]){
                dist[cur.idx+1] = cur.w + 1;
                pq.offer(new Node(cur.idx+1,cur.w+1));
            }
            if(cur.idx*2 <= 100000 && cur.w + 1 <= dist[cur.idx*2]){
                dist[cur.idx*2] = cur.w + 1;
                pq.offer(new Node(cur.idx*2,cur.w+1));
            }

        }
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        count = 0;
        if(N>=K){
            System.out.println(N-K);
            System.out.println(1);
            return;
        }

        dist = new int[100001];
        Arrays.fill(dist,INF);

        pq = new PriorityQueue<>();
        pq.offer(new Node(N,0));
        dist[N]=0;

        solve();

        System.out.println(dist[K]);
        System.out.println(count);

    }

    static class Node implements Comparable<Node>{
        int idx,w;

        public Node(int idx, int w){
            this.idx = idx;
            this.w = w;
        }

        @Override
        public int compareTo(Node o){
            return this.w - o .w;
        }

    }

}