1753번. 최단경로

 

아이디어

하나의 정점에서 다른 모든 정점으로의 최단 경로는 '다익스트라' 알고리즘을 통해서 구할 수 있다.

 

다익스트라 알고리즘은 다음과 같이 동작한다.

 

1. 시작점에서 다른 지점까지의 최단 경로를 표현하는 배열 dist 정의

2. 시작점 -> 시작점 : 0, 나머지는 INF 로 초기화

3. 아직 방문하지 않은 정점 중 가장 최소값을 갖는 정점 방문

4. 해당 정점에서 방문할 수 있는 정점들 갱신

5. 더 이상 방문할 정점이 없을 때까지 3 ~ 4 과정 반복

 

예제를 통해 보면 1, 2 과정을 통해 dist = [0, INF, INF, INF, INF] 가 된다.

3 에 의해서 1번 정점을 방문하고 1번에서 갈 수 있는 2, 3 을 갱신하게 된다.

dist = [0, 2, 3, INF, INF]

 

아직 방문하지 않은 정점(2, 3, 4, 5) 중 2가 가장 최소값을 갖기 때문에 2번 정점을 방문하고 2번에서 갈 수 있는 3, 4 를 갱신한다.

dist = [0, 2, 3 vs (2 + 4), INF vs (2 + 5), INF] = [0, 2, 3, 7, INF]

 

아직 방문하지 않은 정점 (3, 4, 5) 중 3이 가장 최소값을 갖기 때문에 3번 정점을 방문하고 3번에서 갈 수 있는 4 를 갱신한다.

dist = [0, 2, 3, 7 vs (3 + 6), INF] = [0, 2, 3, 7, INF]

 

아직 방문하지 않은 정점 (4, 5) 중 4가 가장 최소값을 갖기 때문에 4번 정점을 방문하고 4번에서는 갈 수 있는 곳이 없으므로 따로 갱신은 하지 않는다.

dist = [0, 2, 3, 7, INF]

 

아직 방문하지 않은 정점 (5) 중 5가 가장 최소값을 갖기 때문에 5번 정점을 방문하고 5번에서 갈 수 있는 1을 갱신한다.

dist = [0 vs (INF + 1), 2, 3, 7, INF] = [0, 2, 3, 7, INF]

 

이 문제에서는 정점의 최대 개수가 20,000, 간선의 최대 비용이 10 으로 최악의 케이스에 발생할 수 있는 비용이 199,990  이므로 INF 대신 199,991 을 사용하면 된다.

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List<Node>[] graph;
    static int[] dist;
    static boolean[] visited;

    static int V;
    static int K;

    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()); // 정점의 개수
        int E = Integer.parseInt(st.nextToken()); // 간선의 개수
        K = Integer.parseInt(br.readLine()) - 1; // 시작 정점

        graph = new List[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
        }

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

            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new Node(to, cost));
        }

        dist = new int[V];
        visited = new boolean[V];
        Arrays.fill(dist, 199991);
        dist[K] = 0;

        dijkstra(K);

        for (int i = 0; i < V; i++) {
            System.out.println(dist[i] == 199991 ? "INF" : dist[i]);
        }
    }

    public static void dijkstra(int from) {
        visited[from] = true;

        List<Node> nodes = graph[from];
        for (int i = 0; i < nodes.size(); i++) {
            Node node = nodes.get(i);
            dist[node.to] = Math.min(dist[node.to], dist[from] + node.cost);
        }

        int next = -1;
        int min = 199991;
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dist[i] < min) {
                next = i;
                min = dist[i];
            }
        }

        if (next == -1) return;
        dijkstra(next);
    }
}

class Node {

    int to;
    int cost;

    Node (int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}