[BOJ] 백준 [1753] 최단경로 JAVA

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

1753번: 최단경로

문제

풀이

nlogn 시간복잡도인 우선순위큐를 이용한 다익스트라 기본 풀이다.

간선의 가중치 낮은 순으로 우선순위큐에 들어가기때문에 n^2 방식인 최소비용탐색하는 시간이 들지 않기때문

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int MAX_DIST = 98765321;
    static int[] dist;
    static int V,E,start;
    static ArrayList<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]); E = Integer.parseInt(input[1]); start = Integer.parseInt(br.readLine());
        dist = new int[V+1];
        Arrays.fill(dist,MAX_DIST);
        list = new ArrayList[V+1];
        for(int i=1;i<=V;i++)
            list[i] = new ArrayList<Node>();
        for(int i=1;i<=E;i++){
            input = br.readLine().split(" ");
            list[Integer.parseInt(input[0])].add(new Node(Integer.parseInt(input[1]),Integer.parseInt(input[2])));
        }
        findShortPath(start);
    }
 
    static void findShortPath(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start,0));
        dist[start] = 0;
        while (!q.isEmpty()){
            Node poll = q.poll();
            if(dist[poll.node] < poll.weight)
                continue;
 
            for (Node next : list[poll.node]) {
                if(dist[next.node] > dist[poll.node] + next.weight){
                    dist[next.node] = dist[poll.node] + next.weight;
                    q.add(new Node(next.node,dist[next.node]));
                }
            }
        }
 
        for(int i=1;i<=V;i++) {
            if(dist[i] == MAX_DIST)
                System.out.println("INF");
            else
                System.out.println(dist[i]);
        }
    }
 
    static class Node implements Comparable<Node>{
        int node;
        int weight;
 
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;
        }
    }
}
 
 
 

근데 왜지 ..? n^2 시간복잡도 방식이 시간이 덜 걸린 이유는 .. ? ㅋㅋ..