[Do It! 코딩테스트 자바편(김종관)] 문제 057(백준 1916번)

느낀점

• 문제 056(백준 1753번)과 거의 똑같은 문제였다.
• 단 차이점이 있는데, 56번에서는 dijkstra 메서드에 있는 if (visited[now.cityNum]) continue;와 비슷한 구문을 지우고 돌려봤는데 맞았다. 반면 57번에서 이 부분을 지우고 돌리니까 26%에서 시간초과가 떴다.

문제

최소비용 구하기 (백준: 1916번)

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int cityCount, busCount;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] minimumFee;
    static boolean[] visited;
    static int startCity, endCity;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        cityCount = Integer.parseInt(br.readLine());
        busCount = Integer.parseInt(br.readLine());

        // 인접리스트 초기화
        for (int i = 0; i <= cityCount; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 1; i <= busCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int fee = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Node(end, fee));
        }

        // 츨발도시와 도착도시 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        startCity = Integer.parseInt(st.nextToken());
        endCity = Integer.parseInt(st.nextToken());
        // 방문배열, 최단경로 배열 초기화
        visited = new boolean[cityCount + 1];
        minimumFee = new int[cityCount + 1];
        for (int i = 1; i <= cityCount; i++) {
            if (i == startCity) {
                minimumFee[i] = 0;
            } else {
                minimumFee[i] = Integer.MAX_VALUE;
            }
        }

        dijkstra();
        System.out.println(minimumFee[endCity]);
    }

    private static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(startCity, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (visited[now.cityNum])
                continue;
            visited[now.cityNum] = true;

            for (Node next : graph.get(now.cityNum)) {
                if (minimumFee[next.cityNum] > minimumFee[now.cityNum] + next.fee) {
                    minimumFee[next.cityNum] = minimumFee[now.cityNum] + next.fee;
                    pq.add(new Node(next.cityNum, minimumFee[next.cityNum]));
                }
            }
        }
    }
}

class Node implements Comparable<Node> {
    int cityNum;
    int fee;

    public Node(int cityNum, int fee) {
        this.cityNum = cityNum;
        this.fee = fee;
    }

    @Override
    public int compareTo(Node node) {
        return this.fee - node.fee;
    }

}