[BOJ_11562 | Floyd]백양로 브레이크

풀이

플로이드 와샬 알고리즘을 응용해야 하는 쉽지만은 않은 문제였던것 같다.

숫자에 의미를 부여하여 그래프를 구성해야 하고, 이 의미를 부여하여 그래프를 완성하는 과정 자체가

생각해내기 쉽지는 않았다.

문제 해결을 위한 생각의 과정은 다음과 같다.

예를 들어 1 2 0 이라는 input이 주어지면

1에서 2로 가는 경로를 dis[1][2] 배열에 생성한다. 즉, 0이라는 값을 배열에 넣어준다는 것이다. 

그리고 여기서 중요한 것이 2에서 1로 가는 경로가 없지만, 1에서 2로 가는 경로가 있기 때문에

양방향의 경로가 연결될 가능성이 있으므로, 1이라는 값을 dis[2][1]에 넣어준다.

다시말해서, 이미 단방향이든, 양방향이든 경로가 있으면 거기에는 도로를 추가할 일이 없으므로 0을 넣어주고

단방향의 경로가 없지만, 반대 방향의 경로가 있다면, 도로를 추가할 가능성이 있으므로 1을 넣어준다는 것이다.

이렇게 배열을 만들고 플로이드 와샬 알고리즘을 돌리면

플로이드 와샬 알고리즘의 수행 결과로 나온 배열은

각 경로별로 추가되어야 하는 양방향 경로의 개수를 값으로 갖게 된다.

간단한 예시를 들자면, 

1 -> 3으로 가는 경로를 구하려고 하는데 

1 -> 2에는 경로가 있고, 

2 -> 3에는 경로가 없고, 대신 3 -> 2에는 경로가 있다고 하자

그러면 dis[1][2] = 0, dis[2][3] = 1, dis[3][2] = 0이 될 것이다.

3 ->2 의 단방향 도로를 양방향으로 만들면 경로가 생긴다.

이 경우 dis[1][3] = dis[1][2] + dis[2][3] = 1로

1개의 추가적인 양방향 도로가 필요하다는 것을 알 수 있다.

소스 코드

import java.util.*;
public class BOJ_11562 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); int m = input.nextInt();
        int[][] dis = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dis[i][j] = 100000;
                if(i==j) dis[i][j] = 0;
            }
        }
        for(int i=0;i<m;i++){
            int i1 = input.nextInt()-1;
            int j1 = input.nextInt()-1;
            int b = input.nextInt();
            if(b==1){
                dis[i1][j1] = 0;
                dis[j1][i1] = 0;
            }else{
                dis[i1][j1] = 0;
                dis[j1][i1] = 1;
            }
        }
        //floyd
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(dis[i][j] > dis[i][k]+dis[k][j])
                        dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
        int num = input.nextInt();
        for(int i=0;i<num;i++){
            int i1 = input.nextInt()-1;
            int j1 = input.nextInt()-1;
            System.out.println(dis[i1][j1]);
        }
    }
}