백준 11562 - 백양로 브레이크

문제

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

리뷰

출발지와 도착지를 입력 받고 최단 경로를 답한다는 점에서
직관적으로 플로이드-워셜로 접근해야 한다는 느낌을 받았다.

로직의 구성은 간단하다. 간선 $i\rightarrow j$를 입력받을 때 양방향일 경우
$j\rightarrow i$의 비용을 0으로 설정해주고, 단방향일 경우 1로 설정해준다.
이렇게 경로에 대한 정보를 설정해준 후 플로이드-워셜을 실행하게 되면
floyd[i][j]의 값은 자연스레 $i\rightarrow j$ 경로를 가능케 하기 위해
바꿔야 하는 최소 일방 통행 길의 수가 된다.

로직의 시간복잡도에서 가장 큰 비중을 차지하는 플로이드-워셜은 $O(N^3)$의
복잡도를 띄지만 $N$이 최대인 250일때도 1500만 가량의 연산을 수행케 되므로
시간 제한인 1초를 무난히 통과할 수 있다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;
import static java.lang.Integer.MAX_VALUE;

import java.io.*;


public class Main {
    static int N, M;
    static int[][] floyd;

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

        floyd = new int[N + 1][N + 1];
        for (int i = 1; i < floyd.length; i++)
            for (int j = 1; j < floyd[i].length; j++) {
                floyd[i][j] = (i == j) ? 0 : MAX_VALUE;
            }

        for (int edge = 0; edge < M; edge++) {
            st = new StringTokenizer(br.readLine());
            int i = parseInt(st.nextToken());
            int j = parseInt(st.nextToken());
            int b = parseInt(st.nextToken());

            floyd[i][j] = 0;
            floyd[j][i] = (b == 0) ? 1 : 0;
        }

        floydWashall();

        int k = parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            int i = parseInt(st.nextToken());
            int j = parseInt(st.nextToken());

            sb.append(floyd[i][j] + "\n");
        }

        System.out.print(sb);
        br.close();
    }

    static void floydWashall() {
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++) {
                    if (floyd[i][k] == MAX_VALUE || floyd[k][j] == MAX_VALUE)
                        continue;

                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
    }

}

결과