[백준] 14496번 : 그대, 그머가 되어

14496번: 그대, 그머가 되어

---

[다익스트라]

다익스트라 알고리즘을 숙지하고 있다면 어렵지 않은 문제. 첫 번째 줄의 시작 정점과 도착 정점을 받아 시작 정점에서 도착 정점까지의 최단 거리를 구하면 된다. 간선은 양방향이라고 주어지진 않았지만, 예제 2번을 보면 간선은 양방향임을 알 수 있다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int tg, d;
        public Point(int tg, int d){
            this.tg = tg;
            this.d = d;
        }
    }
    static final int INF = 1000000000;
    static List<Integer>[] list = new ArrayList[1001];
    static int[] dist = new int[1001];

    static void Dijkstra(int start){

        Queue<Point> pq = new PriorityQueue<>((a, b) -> a.d - b.d);
        dist[start] = 0;
        pq.add(new Point(start, 0));

        while(!pq.isEmpty()){
            Point p = pq.poll();
            int cur = p.tg;
            int d = p.d;

            if(dist[cur] < d) continue;

            for(int next:list[cur]){
                if(dist[next] > d + 1){
                    dist[next] = d + 1;
                    pq.add(new Point(next, d + 1));
                }
            }
        }
    }

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

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

        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
            dist[i] = INF;
        }

        for(int i=0; i<=m-1; i++){
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());

            list[h].add(tg);
            list[tg].add(h);
        }

        Dijkstra(target);
        System.out.println(dist[goal] == INF ? -1 : dist[goal]);
    }
    
}