[백준 1753] 최단경로 (JAVA)

문제

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

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

1753번: 최단경로

 

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1

0
2
3
7
INF

---

다익스트라 알고리즘을 구현하면 되는 문제이다.

 

ArrayList<Node> graph [] 배열에 주어진 노드와 가중치를 저장하고 다익스트라 알고리즘을 구현하자.

 

다익스트라 알고리즘을 사용하면 시작 노드부터 모든 노드 까지의 최단 거리 배열을 구할 수 있다.

 

초기에는 시작 노드를 제외한 나머지 노드에 대한 최단 거리 배열을 INF(0x7ffffff) 로 초기화한다.(시작노드는 0으로)

 

그리고 현재 최단 거리 배열에서 값이 가장 작은 노드를 선택하여, (이 부분은 우선순위큐를 사용하는 것이 편하다.)

 

해당 노드에 연결된 에지를 탐색하여 다른 노드들의 값을 업데이트한다.

 

업데이트 정책은 Min(선택한 노드의 dist 값 ,  edge + 연결된 노드의 dist 값) 이다.

 

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

public class Main {
    static int INF = Integer.MAX_VALUE;
    static ArrayList<Node> graph[];

    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 stk = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(stk.nextToken()); // 노드 개수
        int e = Integer.parseInt(stk.nextToken()); // 에지 개수

        stk = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(stk.nextToken()); // 시작점

        graph = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < e; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());

            graph[a].add(new Node(b, w));
        }

        int[] dist = new int[v + 1];
        boolean[] visited = new boolean[v + 1];
        for (int i = 1; i <= v; i++) {
            dist[i] = INF;
        }

        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (visited[cur.toNode]) continue; // 이미 방문?
            visited[cur.toNode] = true;
            for (int i = 0; i < graph[cur.toNode].size(); i++) {
                Node t = graph[cur.toNode].get(i);
                int next = t.toNode;
                int val = t.e;
                if (dist[next] > dist[cur.toNode] + val) {
                    dist[next] = dist[cur.toNode] + val;
                    q.add(new Node(next, dist[next]));
                }
            }
        }

        for (int i = 1; i <= v; i++) {
            if (!visited[i])
                bw.write("INF\n");
            else bw.write(dist[i] + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    static class Node implements Comparable<Node> {
        int toNode;
        int e;

        public Node(int toNode, int e) {
            this.toNode = toNode;
            this.e = e;
        }

        public int compareTo(Node n) {
            if (this.e > n.e)
                return 1;
            else
                return -1;
        }
    }
}