[백준] 1753번 - 최단경로 (Gold 4)

문제 링크

백준 1753번 - 최단경로 (Gold 4)

문제 설명

가중치가 주어진 방향 그래프에서 시작점이 주어져 있을 때 각 정점까지의 최단거리를 출력한다.
만일 도달이 불가능하다면, INF를 출력한다.

정답 코드 및 설명

전형적인 다익스트라(Dijkstra) 알고리즘 문제이다.
다익스트라 알고리즘은 아래와 같다.

1. 모든 노드의 값을 INF로 채우고, 시작점은 0으로 둔다.
2. 이미 탐색한 점의 집합 S에 시작점을 추가하고, 현재 점 V를 시작점으로 둔다.
3. 집합 S에서 도달할 수 있는 노드들의 값을 현재 노드의 값과 V 노드의 값 + V에서부터의 최단거리 중 작은 것으로 둔다.
4. 집합 S에 포함되어 있지 않은 노드들의 값 중 최소인 점을 현재 점 V로 두고, S에 V를 추가한다.
5. 3, 4를 더 이상 집합 S에 원소를 추가할 수 없을 때까지 반복한다.

실제 코드로 구현하기 위해 최소힙을 사용하는 우선순위 큐를 사용하였다.
코드에서는 3의 과정에서 우선순위 큐에 S에서 도달할 수 있는 노드를 전부 추가한다.
4의 과정에서는 우선순위 큐에서 가장 먼저 나오는 원소를 사용하는데, 이 때 이미 체크한 원소가 또 나올 수 있다.
이를 방지하기 위해 이미 방문한 점인지를 체크하는 과정이 52행이다.

import java.io.*;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1753 {

    final static int INF = 200001;

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

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());
        LinkedList<Edge>[] edge = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            edge[i] = new LinkedList<>();
        }
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            edge[start].add(new Edge(end, Integer.parseInt(st.nextToken())));
        }
        int[] ans = dijkstra(edge, k - 1);
        for (int i = 0; i < v; i++) {
            if (ans[i] != INF)
                sb.append(ans[i]);
            if (ans[i] == INF)
                sb.append("INF");
            sb.append('\n');
        }
        bw.write(sb.toString());
        bw.close();
    }

    static int[] dijkstra(LinkedList<Edge>[] edge, int k) {
        int[] dist = new int[edge.length];
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        pq.offer(new Vertex(k, 0));
        dist[k] = 0;
        while (!pq.isEmpty()) {
            Vertex curr = pq.poll();
            // 이미 방문한 점은 스킵
            if (dist[curr.node] < curr.minDist)
                continue;
            // 이웃한 점 확인
            Iterator<Edge> iter = edge[curr.node].iterator();
            while (iter.hasNext()) {
                Edge e = iter.next();
                // 새 경로가 더 가깝다면 갱신
                if (dist[curr.node] + e.dist < dist[e.end]) {
                    dist[e.end] = dist[curr.node] + e.dist;
                    pq.offer(new Vertex(e.end, dist[e.end]));
                }
            }
        }
        return dist;
    }
}

class Vertex implements Comparable<Vertex> {

    final static int INF = 200001;

    int node, minDist;

    Vertex(int node, int minDist) {
        this.node = node;
        this.minDist = minDist;
    }

    public int compareTo(Vertex v) {
        return this.minDist - v.minDist;
    }
}

class Edge {
    int end, dist;

    Edge(int end, int dist) {
        this.end = end;
        this.dist = dist;
    }
}