[백준][다익스트라][Java] 1753. 최단경로 : 골드 4

문제 링크 : https://www.acmicpc.net/problem/1753

 

 

이 문제는 특정 시작 정점에서 모든 정점까지의 최소 비용을 구하는 것이다.
간선마다 가중치가 있고 음수 가중치는 없기 때문에 다익스트라 알고리즘을 사용할 수 있다.

 

1. 시작 정점까지의 거리는 0으로 둔다.
2. 현재까지 발견된 경로 중 가장 비용이 작은 정점을 먼저 선택한다.
3. 그 정점을 거쳐서 갈 수 있는 다른 정점들의 거리를 다시 계산한다.
4. 더 짧은 경로가 발견되면 해당 값을 변경한다.

이 과정에서 가장 작은 비용을 가진 정점을 빠르게 찾기 위해 PriorityQueue를 사용했다!

 

visited 상태값을 관리하는 순간 망하는 것이여.... 

 

비슷한 문제를 풀고 싶으면, https://cse-gr.tistory.com/229 참고하세용

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


import java.util.*;

public class Main{
    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 start = Integer.parseInt(br.readLine());

        List<Node>[] arr = new ArrayList[V+1];

        for(int i = 1; i <= V; i++){
            arr[i] = new ArrayList<>();
        }
        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            arr[s].add(new Node(e, cost));
        }
        
        int[] costs = new int[V+1];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));


        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            int e = cur.e;
            int cost = cur.cost;

            if(cost > costs[e]) continue;

            for (Node next : arr[e]) {
                int nextE = next.e;
                int newCost = cost + next.cost;
                if (costs[nextE] <= newCost)
                    continue;

                costs[nextE] = newCost;
                pq.add(new Node(nextE, newCost));
            }
        }

        for(int i = 1; i <= V; i ++){
            if(costs[i] == Integer.MAX_VALUE) System.out.println ("INF");
            else System.out.println(costs[i]);
        }
    }

    public static class Node implements Comparable<Node>{
        int e, cost;

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

        public int compareTo(Node o){
            return this.cost - o.cost;
        }
    }
}