[BaekJoon] 11562 백양로 브레이크 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int buildingCount;
    static int roadCount;
    static int questionCount;
    static boolean[] isCalculated;
    static int[][] questions;
    static int[][] minConversionCounts;
    static Map<Integer, List<Road>> roads;

    static void input() {
        Reader scanner = new Reader();

        buildingCount = scanner.nextInt();
        roadCount = scanner.nextInt();
        isCalculated = new boolean[buildingCount + 1];
        minConversionCounts = new int[buildingCount + 1][buildingCount + 1];
        roads = new HashMap<>();
        for (int buildingNum = 1; buildingNum <= buildingCount; buildingNum++) {
            Arrays.fill(minConversionCounts[buildingNum], Integer.MAX_VALUE);
            roads.put(buildingNum, new ArrayList<>());
        }

        for (int road = 0; road < roadCount; road++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int bidirectional = scanner.nextInt();

            roads.get(start).add(new Road(end, 0));
            roads.get(end).add(new Road(start, (bidirectional + 1) % 2));
        }

        questionCount = scanner.nextInt();
        questions = new int[questionCount][2];
        for (int idx = 0; idx < questionCount; idx++) {
            questions[idx][0] = scanner.nextInt();
            questions[idx][1] = scanner.nextInt();
        }
    }

    /*
     * 다익스트라 알고리즘을 이용하여 해결한다
     * 주어진 길이 양방향 길이라면
     *  - 양방향으로 가중치 0의 간선을 추가하고
     * 주어진 길이 일방통행 길이라면
     *  - 시작 건물부터 도착 건물까지는 가중치 0의 간선을 추가하지만
     *  - 도착 건물부터 시작 건물까지는 가중치 1의 간선을 추가한다
     * 
     * 다익스트라에서 가중치를 일방통행에서 양방향으로 바꾼 길의 개수라고 두고
     * 시작 건물부터 다른 모든 건물들로의 최단 거리(최저 가중치)를 구한다
     * 
     * 만약 주어진 질문에서 아직 다익스트라를 돌리지 않은 시작 건물에 대한 질문을 물어본다면
     * 다익스트라를 돌린 후에 시작 건물부터 도착 건물까지의 최저 가중치를 출력한다
     * 만약 주어진 질문에서 다익스트라를 이미 돌린 시작 건물에 대한 질문을 물어본다면
     * 다시 다익스트라를 돌리지 않고 바로 시작 건물부터 도착 건물까지의 최저 가중치를 출력한다
     */
    static void solution() {
        StringBuilder answer = new StringBuilder();
        for (int questionIdx = 0; questionIdx < questionCount; questionIdx++) {
            int startBuilding = questions[questionIdx][0];
            int endBuilding = questions[questionIdx][1];
            if (isCalculated[startBuilding]) {
                answer.append(minConversionCounts[startBuilding][endBuilding]).append('\n');
                continue;
            }

            dijkstra(startBuilding, minConversionCounts[startBuilding]);
            isCalculated[startBuilding] = true;
            answer.append(minConversionCounts[startBuilding][endBuilding]).append('\n');
        }

        System.out.print(answer);
    }

    static void dijkstra(int startBuilding, int[] weights) {
        Queue<Road> queue = new PriorityQueue<>();

        queue.offer(new Road(startBuilding, 0));
        weights[startBuilding] = 0;

        while (!queue.isEmpty()) {
            Road cur = queue.poll();
            if (weights[cur.buildingNum] < cur.conversionCount) {
                continue;
            }

            for (Road next : roads.get(cur.buildingNum)) {
                int nextBuilding = next.buildingNum;
                int nextConversionCount = cur.conversionCount + next.conversionCount;

                if (weights[nextBuilding] > nextConversionCount) {
                    weights[nextBuilding] = nextConversionCount;
                    queue.offer(new Road(nextBuilding, nextConversionCount));
                }
            }
        }
    }

    static class Road implements Comparable<Road> {
        int buildingNum;
        int conversionCount;

        public Road(int buildingNum, int conversionCount) {
            this.buildingNum = buildingNum;
            this.conversionCount = conversionCount;
        }

        @Override
        public int compareTo(Road o) {
            return conversionCount - o.conversionCount;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}