백준 1753번 최단경로

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

 

- 최단경로 다익스트라 알고리즘

• 가중치 개념 O
• 한 노드 기준 최소경로 값 구하기

 

- 나의 풀이

 

 

 - 나의 코드

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    
    static class Edge {
        int to; // 도착 정점
        int weight; // 가중치
        
        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    static int V, E, start; // 정점 개수, 간선 개수, 시작점
    static ArrayList<Edge>[] graph; // 그래프 정보 저장 배열
    static int[] distance; // 최단거리 배열
    
    public static int sToi(String s) {
        return Integer.parseInt(s);
    }
    
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        
        V = sToi(st.nextToken());
        E = sToi(st.nextToken());
        
        start = sToi(br.readLine());
        
        distance = new int[V+1]; // 인덱스 0 사용 X ~> 정점 번호에 맞춰서 배열 인덱스 사용 위함
        graph = new ArrayList[V+1];
        
        // 최단거리 배열 초기화
        for(int i=0; i<= V; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[start] = 0; // 시작점 자신은 0
        
        // 그래프 초기화
        for(int i=0; i<=V; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = sToi(st.nextToken()); // 출발
            int v = sToi(st.nextToken()); // 도착
            int w = sToi(st.nextToken()); // 가중치
            
            graph[u].add(new Edge(v, w));
        }
        
        // 다익스트라
        PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight); // 오름차순 x-y, 내림차순 y-x
        // 람다식 추가설명
        // x.weight - y.weight의 결과가 음수일 때 x가 먼저, 양수일 때 y가 먼저 배치
        // 작은 값(가중치)이 앞에 오도록 정렬되므로 최소 힙
        
        pq.add(new Edge(start, 0)); // 시작점 자신은 0
        
        while(!pq.isEmpty()) {
            Edge now = pq.poll();
            
            if(distance[now.to] < now.weight) {
                continue;
            }
            
            for(int i=0; i<graph[now.to].size(); i++) {
                Edge tmp = graph[now.to].get(i);
                int next = tmp.to;
                int weight = tmp.weight;
                
                if(distance[next] > distance[now.to] + weight) {
                    distance[next] = distance[now.to] + weight;
                    pq.offer(new Edge(next, distance[next]));
                }
            }
        }
        
        // 출력
        for(int i=1; i<=V; i++) { // 인덱스 0 사용 X ~> 정점 번호에 맞춰서 배열 인덱스 사용 위함
            if(distance[i] == Integer.MAX_VALUE) {
                System.out.println("INF"); // 경로가 존재하지 않는 경우 INF
            } else {
                System.out.println(distance[i]);
            }
        }
        
    }
}