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

플로이드와샬을 활용하는 문제였다.

기존 플로이드와샬 문제와는 접근법을 다르게해야 풀 수 있는 문제였다. 이 문제 같은 경우는 단방향에서 양방향으로 바꿔야하는 길의 수, 즉 단방향으로 연결되어 있는 곳에 반대 반향의 길을 연결해야하는 갯수를 체크해야하는 문제이다. 이 문제 같은 경우는 N의 최대값이 250이기에 최단거리를 구하는 플로이드와샬 기법을 활용할 수 있다. 다만, 기존의 플로이드와샬 문제와는 다르게 경로의 비용 선정에 있어서 조금 다른 부분이 필요하다. 즉, 구해야하는 것이 단방향에서 반대방향의 갯수이기에 단방향이 입력으로 들어왔을 때 반대방향에 대해서 1, 그외에는 0으로 설정해주는 것이 필요하다. 다시말해 기존 경로에 대해서는 0, 새로 생성할(단뱡향에서의 반대방향)경로에 대해서는 1로 설정을 해주고, 플로이드 와샬알고리즘을 활용하면 된다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_11562_백양로브레이크 {
    static int N;
    static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
 
        map = new int[N + 1][N + 1];
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] = i == j ? 0 : Integer.MAX_VALUE / 2;
            }
        }
 
        //기본적인 floyd 문제와 다르게 주어진 경로에 대해선 비용 0으로 설정
        //양방향 통행으로 바꿔야하는 단방향의 갯수를 체크 == 단방향이 주어졌을 때 그 단방향의 반대 방향의 비용을 1로 설정
        //그후 floyd 탐색
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int isBidirectional = Integer.parseInt(st.nextToken());
 
            if (isBidirectional == 1) {        //양방향일 경우 통행하는데 있어 비용이 소요되지 않는다
                map[start][end] = 0;
                map[end][start] = 0;
            } else {                            //단방향일 경우 end에서 start로 가는데 비용이 소요된다
                map[start][end] = 0;
                map[end][start] = 1;
            }
        }
 
        floyd();
 
        int input = Integer.parseInt(br.readLine());
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
 
            sb.append(map[start][end] + "\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i != j && map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
    }
}