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

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

1753번: 최단경로

풀이

전형적인 다익스트라 알고리즘 문제이다.

dp와 bfs를 이용해서 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

 

다익스트라에 대해서 잘 모르면 아래 링크를 먼저 보는 걸 추천한다.

자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리

위 문제의 예제를 살펴보면 아래와 같다.

1. dp 배열을 모두 INF(Integer.MAX_VALUE)로 초기화한다.

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
INF	INF	INF	INF	INF

2. 시작 노드 '1'을 0으로 변경하고, '1'에서 갈 수 있는 노드들의 값을 변경해준다. 

    변경 후에는 노드 '2'와 '3'을 우선순위 큐에 입력한다.

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
0	2 (0 + 2)	3 (0 + 3)	INF	INF

3. 현재 이동할 수 있는 노드 중에 아직 방문하지 않은 노드를 가까운 곳부터 방문해서 dp 배열을 갱신해준다.

    비교적 가중치가 적은 노드 '2'를 방문 후에 노드 '4'에 갈 수 있는 최단 경로를 dp 배열에 입력 후 우선순위 큐에 '4' 입력

dp[1]	dp[2]	3	dp[4]	dp[5]
0	2	3	7 ( 2+ 5)	INF

4. 다음 노드 '3'을 방문 후에 '4'로 갈 수 있는 최단 경로를 dp 배열에 넣는다. 현재 dp[4]에는 7이 들어가 있다.

    dp[4](도착 노드) > dp[3](현재 노드) + 6 (노드 '3'에서 노드 '4'까지의 가중치)를 만족하지 않기 때문에 갱신하지 않는다.

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
0	2	3	7	INF

더 이상 방문할 수 있는 노드가 없으므로 bfs를 종료한다.

 

dp[도착 노드] > dp[현재 노드] + 현재 노드에서 도착 노드까지의 가중치 조건이 만족하면 갱신해주고, 그렇지 않다면 갱신해주지 않으면 된다.

 

<최종코드>

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

public class Main {
    public static class Node implements Comparable<Node> {
        int e;
        int v;
		
        public Node (int e, int v) {
            this.e = e;
            this.v = v;
        }
		
        public int compareTo(Node o) {
            return this.v - o.v;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int V = Integer.valueOf(st.nextToken());
        int E = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(br.readLine());
		
        ArrayList<Node>[] arrList = new ArrayList[V+1];
        for (int i=1; i<=V; i++) {
            arrList[i] = new ArrayList<Node>();
        }
		
        for (int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
			
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
			
            arrList[start].add(new Node(end, value));
        }
		
        int[] dp = new int[V+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
		
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(K, 0));
        dp[K] = 0;
		
        while (!pq.isEmpty()) {
            Node now = pq.poll();
			
            for (Node next : arrList[now.e]) {
                if (dp[next.e] > dp[now.e]+ next.v) {
                    dp[next.e] = dp[now.e] + next.v;
                    pq.add(new Node(next.e, dp[next.e]));
                }
            }
        }
		
        for (int i=1; i<=V; i++) {
            if (dp[i] == Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dp[i]);
        }
    }
}