[백준] 1753 최단경로 (JAVA)

 

풀이

위 문제는 자료구조에서 접할수있는 기본적인 그래프 문제이다. 이 문제에서는 전부 양의 간선이고 방향이 있기에 다익스트라 알고리즘을 사용하였다 또한 그래프를 탐색할때는 우선순위 큐를 사용했는데 우선순위큐를 사용한 이유에 대해서는 조금더 고민을 해보아야 할것 같다. 

 

코드

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

class Main {

    static class Node implements Comparable<Node> {
        int end;
        int weight;

        public Node(int end, int wright) {
            this.end = end;
            this.weight = wright;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static List<Node>[] list;
    static int dist[];
    static int v, e, k;
    static int INF = 999999999;


    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());

        dist = new int[v+1];
        list = new List[v+1];

        Arrays.fill(dist, INF);
        for(int i=1; i<=v; i++) list[i] = new ArrayList<Node>();

        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list[start].add(new Node(end, weight));
        }

        StringBuilder sb = new StringBuilder();
        dijkstra(k);

        for(int i=1; i<=v; i++){
            if(dist[i] == INF) sb.append("INF\n");
            else sb.append(dist[i] + "\n");
        }

        bw.write(sb.toString());

        bw.close();
        br.close();
    }

    public static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        boolean [] check = new boolean[v+1];
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node curNode = pq.poll();
            int cur = curNode.end;
            if(check[cur]) continue;
            check[cur] = true;

            for (Node node: list[cur]) {
                if(dist[node.end] > (dist[cur] + node.weight)){
                    dist[node.end] = dist[cur] + node.weight;
                    pq.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }

}