백준 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.StringTokenizer;

public class Main {

    private static boolean visited [];
    private static int dist[];
    private static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    private static int v,e, start;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        initGraph(br,st);
        dijkstra();
        print();


    }

    private static void initGraph(BufferedReader br, StringTokenizer st) throws IOException {
        v = Integer.parseInt(st.nextToken());   // 정점의 개수
        e = Integer.parseInt(st.nextToken());   // 간선의 개수

        visited = new boolean[v+1];
        dist = new int[v+1];
        Arrays.fill(dist,Integer.MAX_VALUE);

        for(int i=0; i<=v; i++) graph.add(new ArrayList<>());

        start = Integer.parseInt(br.readLine());
        dist[start] = 0;
        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int stNode = Integer.parseInt(st.nextToken());
            int edNode = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(stNode).add(new Node(edNode, cost));
        }
    }

    private static void dijkstra(){
        for(int i=0; i<v; i++){
            int curCost = Integer.MAX_VALUE;
            int curIdx = 0;

            // 방문하지 않은 노드중 최소 값 찾기
            for(int j=1; j<v+1; j++){
                if(!visited[j] && dist[j] < curCost){
                    curCost = dist[j];
                    curIdx = j;
                }
            }

            visited[curIdx] = true;

            for(int j=0; j< graph.get(curIdx).size(); j++){
                Node node = graph.get(curIdx).get(j);

                dist[node.idx] = Math.min(dist[node.idx], dist[curIdx] + node.cost);
            }
        }
    }

    private static void print(){
        for(int i=1; i<=v; i++){
            if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }
}

class Node{
    int idx;
    int cost;

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