문제 설명

문제 분석

슈도코드

구현

<aside> 💡 현재 사용할 수 있는 노드를 우선순위 큐에 넣은 이유

현재 연결된 노드 중 가장 적은 비용을 지니고 있는 노드를 빠르고 간편하게 찾을 수 있기 때문이다. 우선순위 큐는 데이터가 새롭게 들어올 때마다 자동으로 정렬한다. 정렬 기준은 Node 클래스에서 compareTo() 함수를 이용해 설정할 수 있다.

</aside>

public class 최소비용구하기_1916 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 도시의 개수
        int M = Integer.parseInt(reader.readLine()); // 버스의 개수
        boolean[] visited = new boolean[N + 1]; // 방문 배열

        int[] dist = new int[N + 1]; // 최단 거리 배열
        Arrays.fill(dist, Integer.MAX_VALUE);

        ArrayList<Node>[] cities = new ArrayList[N + 1]; // 인접 리스트 그래프
        for (int i = 0; i <= N; i++) {
            cities[i] = new ArrayList<>();
        }

        StringTokenizer tokenizer;
        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int s = Integer.parseInt(tokenizer.nextToken());
            int e = Integer.parseInt(tokenizer.nextToken());
            int v = Integer.parseInt(tokenizer.nextToken());

            cities[s].add(new Node(e, v));
        }

        tokenizer = new StringTokenizer(reader.readLine());
        int startCity = Integer.parseInt(tokenizer.nextToken());
        int endCity = Integer.parseInt(tokenizer.nextToken());

        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(startCity, 0));
        dist[startCity] = 0;

        while (!q.isEmpty()) {
            Node curCity = q.poll();
            if (visited[curCity.target]) continue;

            visited[curCity.target] = true;
            for (Node next : cities[curCity.target]) {
                // [(현재 노드 + 비용) < 타겟 노드] 면 값 업데이트
                if(!visited[next.target] && dist[next.target] > dist[curCity.target] + next.value) {
                    dist[next.target] = dist[curCity.target] + next.value;
                    q.add(new Node(next.target, dist[next.target]));
                }
            }
        }

        System.out.println(dist[endCity]);
    }

    static class Node implements Comparable<Node> {
        int target;
        int value;

        public Node(int target, int value) {
            this.target = target;
            this.value = value;
        }

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