[백준]최단경로(1753)

• 다익스트라 알고리즘 문제이다.
• 특징
  • 각 정점을 최대 한번씩만 방문하여 최단 거리를 확정한다. ( 음의 가중치를 가질 수 없다. )
  • 아직 방문하지 않은 정점들 중 최단거리인 점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식으로 진행된다.
  • 총 V*V번 연산이 필요하다. 따라서 O(V^2)의 시간복잡도를 가진다.
  • 방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 혹은 힙 자료구조를 이용하면 더욱 개선된 알고리즘이 가능하다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static class Point implements Comparable<Point>{
        int x, y;

        Point(int x, int y) {
            this.x = x;     // 도착점
            this.y = y;     // 비용       
        }

        @Override
        public int compareTo(Point o) {     // 비용에 따라 정렬
            // TODO Auto-generated method stub
            return this.y - o.y;
        }
    }

    static boolean[] visited;   // 방문 체크
    static List<Point> list[];
    static int[] value;
    static PriorityQueue<Point> pq = new PriorityQueue<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();   // 정점
        int E = sc.nextInt();   // 간선
        int K = sc.nextInt();   // 시작 정점

        list = new ArrayList[V+1];

        value = new int[V+1];
        visited = new boolean[V+1];
        Arrays.fill(value, Integer.MAX_VALUE);  // max값으로 채우기
        value[K]=0;

        for(int i=0;i<=V;i++) {
            list[i] = new ArrayList<>();
        }

        // 인접 리스트
        for(int i=0;i<E;i++) {
            int a = sc.nextInt();   // 시작점
            int b = sc.nextInt();   // 도착점
            int c = sc.nextInt();   // 비용
            list[a].add(new Point(b,c));
        }
        pq.add(new Point(K,0));     // 우선순위 큐에 시작점을 넣는다.
        solve(K);
        for(int i=1;i<=V;i++) {
            System.out.println(value[i]==Integer.MAX_VALUE?"INF":value[i]);     // 경로가 없으면 max 값이다. 그러므로 INF를 출력       
        }
    }

    static void solve(int k) {
        while(!pq.isEmpty()) {
            int now = pq.poll().x;      // 남은 값 중에 비용이 가장 작은 정점

            if(visited[now]) continue;  // 이미 방문했다면 다음으로..
            visited[now]=true;          // 방문 체크

            for(Point i:list[now]) {    // 선택된 정점에 연결 리스트 확인
                if(value[i.x] > value[now]+i.y) {    // i 비용과 now를 경유해서 들어온 비용을 비교               
                    value[i.x] = value[now]+i.y;
                    pq.add(new Point(i.x,value[i.x]));
                }
            }

        }

    }
}