[JAVA] 백준 1753번 : 최단경로

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

1753번: 최단경로

---

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

public class Main {
    static int V, E, u, v, w;
    static ArrayList<Edge>[] graph;
    static int[] answer;

    private static class Edge implements Comparable<Edge> {
        int node;
        int weight;

        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            if (this.weight > o.weight) return 1;
            return -1;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        graph = new ArrayList[V + 1];
        answer = new int[V + 1];
        Arrays.fill(answer, Integer.MAX_VALUE);
        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }

        int start = Integer.parseInt(br.readLine());
        while (E-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            graph[u].add(new Edge(v, w));
        }
        dijkstra (start);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if(answer[i] == Integer.MAX_VALUE)
                sb.append("INF\n");
            else
                sb.append(answer[i]+"\n");
        }
        System.out.println(sb);
    }

    private static void dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
        answer[start] = 0;
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            if(now.weight > answer[now.node]) continue; //최소 안되면 탐색 금지

            for (Edge next : graph[now.node]) {
                if(answer[next.node] > now.weight + next.weight) {//최솟값이면 갱신
                    answer[next.node] = now.weight + next.weight;
                    pq.add(new Edge(next.node, answer[next.node]));
                }
            }
        }
    }
}

💡 다익스트라

풀이

• 처음에 일반적인 BFS로 풀었지만 시간초과 발생함
• 일반적인 BFS가 아닌 다익스트라로 풀어야 함❗❗
  • Edge 정렬을 weight 기준으로 오름차순 정렬
  • poll 된 순간의 누적 weight 판단 -> answer[now]보다 작은 값이면 다시 탐색 / 아니면 스킵 
  • => 최솟값이 되는 경우에 대해서만 탐색하게 함 (즉 현재 큐에 있는 노드들의 weight는 모두 제일 마지막으로 갱신된 최솟값)