[백준] 11562. 백양로 브레이크

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

11562번: 백양로 브레이크

플로이드 워셜 알고리즘을 통해 간단한 풀이가 나오는 문제이다. 그런데 나는 플로이드는 알았지만 알고리즘을 적절하게 사용하는 아이디어를 떠올리지 못해서 못 푼 문제이다.

• 양방향으로 바꿔야 하는 길의 수를 찾아야 한다. 
• 따라서 양방향으로 바꿔줄 필요가 없으면, 길을 1번 건너든 2번 건너든 같다.
• 즉, start 노드와 end 노드가 양방향 길을 가졌으면, dist[start][end] = 0, dist[end][start] = 0으로 초기화하여, 양방향으로 바꿀 길이 필요 없음을 반영한다. 반면 단방향 길을 가졌으면, dist[start][end] = 0, dist[end][start] = 1로 초기화하여, end에서 start로 가기 위해서는 1개의 다리를 양방향으로 바꿔야 한다는 것을 반영한다. 
• 마지막으로 플로이드 워셜 알고리즘을 적용하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    dist[i][j] = Integer.MAX_VALUE; // 초기값은 MAX
                }
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int command = Integer.parseInt(st.nextToken());
            // 단방향
            if (command == 0) {
                dist[start][end] = 0;
                dist[end][start] = 1; // end에서 start로 가기 위해서는 1개의 다리를 양방향으로 바꿔야 함
            }
            // 양방향
            if (command == 1) {
                dist[start][end] = 0;
                dist[end][start] = 0;
            }
        }
        // 플로이드
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // 더하기 전, 하나라도 MAX 값을 가지면 패스
                    if (dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE) {
                        continue;
                    }
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 결과 출력
        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            System.out.println(dist[start][end]);
        }
    }
}