[다이내믹 프로그래밍] 백준 1753번 최단경로 [Java]

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.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static List<List<Node>> graph;
    static int[] results;

    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.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();
        results = new int[V + 1]; // 노드 별 최소 가중치를 저장할 배열
        
        for (int i = 0; i < V + 1; i++) {
        	graph.add(new ArrayList<>()); // 0~V까지 인접노드들을 저장할 리스트 생성 (0은 무시됨)
        }
        
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(u).add(new Node(v, w));
        }
        
        Arrays.fill(results, Integer.MAX_VALUE);
        
        dijkstra(K);
        results[K] = 0;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < V + 1; i++) {
            if (results[i] == Integer.MAX_VALUE) {
                sb.append("INF").append("\n");
            } else {
                sb.append(results[i]).append("\n");
            }
        }
        System.out.print(sb);
    }

    static void dijkstra(int k) {
        PriorityQueue<Node> que = new PriorityQueue<>((o1, o2) -> {
            return o1.cost - o2.cost;
        });

        que.add(new Node(k, 0));

        while (!que.isEmpty()) {
            Node curNode = que.poll();

            for (Node node : graph.get(curNode.n)) {
            	int nowCost = results[node.n];
                int newCost = curNode.cost + node.cost;
                if (nowCost > newCost) {
                    results[node.n] = newCost;
                    que.add(new Node(node.n, newCost));
                }
            }
        }
    }
}

class Node {
    int n; //노드의 숫자
    int cost; //노드에 도착할 때까지의 비용

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

 

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

 

BFS문제로 생각해서 시간을 많이 잡아먹혔다.

다이나믹 프로그래밍으로 풀었어야 했다.

다익스트라 알고리즘의 기본