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

문제 (Gold 5)

 

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

13549번: 숨바꼭질 3

---

풀이

처음에 단순히 BFS ( 1차원 배열 탐색 ) 으로 풀었더니 당연히! 시간초과가 났다.

그래서 방문하는 인덱스마다의 최단거리를 구하는 다익스트라 알고리즘 사용!

코드

package shortestPath;

import java.util.*;
import java.io.*;

public class Main_13549_숨바꼭질3{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        System.out.println(dijkstra(N, K));;

    }

    private static int dijkstra(int n, int k) {
        PriorityQueue<int[]> q = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1[1], o2[1])));
        int[] dist = new int[100001];
        Arrays.fill(dist, Integer.MAX_VALUE);

        q.offer(new int[]{n, 0});
        dist[n] = 0;
        while (!q.isEmpty()){
            int[] cur = q.poll();
            if(dist[cur[0]] < cur[1]) continue;
            if(cur[0] == k){
                break;
            }
            int[] ni = new int[]{cur[0]-1, cur[0]+1, cur[0]*2};     // 갈 수 있는 인덱스
            for(int i =0 ; i < 3; i++){
                if(0<=ni[i]&&ni[i]<100001){
                    int sec = (i == 0 || i == 1)? 1:0;  // *2 는 순간이동이므로 시간이 추가되지 않음
                    if(dist[ni[i]] > dist[cur[0]] + sec){
                        q.offer(new int[]{ni[i], dist[cur[0]] + sec});
                        dist[ni[i]] = dist[cur[0]] + sec;
                    }
                }
            }
        }

        return dist[k];
    }
}

제출

오래도 걸렸다,,,, 7트만에 성공!!!!!!!!