[BOJ] 백준 11562번 : 백양로 브레이크 (JAVA)

문제

서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공사가 진행되면서 어떻게 한 건진 알 수 없지만 일방통행만 가능한 길이 많이 늘고 말았다.

 

컴퓨터과학과 학생 남규는 전공 수업을 듣고 교양 수업을 들으러 가던 중 길을 잃어 3일 밤낮을 헤매다가 공학관에서 종합관으로 가는 길은 존재하지 않는다는 결론을 내렸다.

 

3일 사이에 과제도 내지 못하고 출석도 하지 못해 학사경고 위기에 처한 남규는 전공을 살려 현재 일방통행인 길들 중 반드시 양방향으로 바꿔야만 하는 길이 몇 개인지 조사해 학교에 건의하기로 마음을 먹었다.

 

남규는 여러 건물들 사이를 직접 잇는 길들을 모두 조사했고, 그 중 어떤 길들이 일방통행인지, 또는 양방향 통행이 가능한지를 모두 체크했다.

남규의 프로그램은 간단하다. 출발지와 도착지를 입력하면 도착지까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야만 하는지를 출력해준다. 프로그램이 완성되었다는 소문이 퍼지자, 남규처럼 길을 잃고 헤맨 경험이 있는 학생들은 남규에게 묻기 시작했다.

 

"공학관에서 대강당 갈 수 있어?"

 

"상경대 별관에서 학관으로는?"

 

남규는 매번 손으로 타이핑해 입력하고 결과를 보내주는 데에 지치고 말았다.

 

결국 앓아누운 남규를 위해 학생들의 질문을 해결할 새로운 프로그램을 만들어보자.

 

 

입력

첫 줄에 Y대학교 건물의 수 n과 길의 수 m이 주어진다. (n ≤ 250, m ≤ n * (n - 1) / 2 )

다음 m줄에 걸쳐, u v b (1 ≤ u ≤ n, 1 ≤ v ≤ n, u != v, b = 0 또는 1) 의 형태로 길에 대한 정보가 주어진다.

b가 0일 경우 u에서 v로 가는 일방통행 길인 것이고, b가 1일 경우 u와 v를 잇는 양방향 길이다.

 

어떤 두 건물 사이를 잇는 길은 최대 한 개이다.

다음 줄에 학생들의 질문의 수 k가 주어진다. (1 ≤ k ≤ 30,000)

다음 k줄에 걸쳐 s e (1 ≤ s ≤ n, 1 ≤ e ≤ n)의 형태로 학생들의 질문들이 주어진다.

이는 질문한 학생이 건물 s에서 건물 e로 가고 싶다는 의미이다.

 

 

출력

출력은 k줄에 걸쳐 이루어진다.

각 질문에 대해, 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 출발지에서 도착지로 갈 수 있는지를 출력한다.

모든 길을 양방향으로 바꾸더라도 서로 도달 불가능한 건물은 없다.

 

 

풀이

플로이드 와샬 알고리즘을 응용하는 문제였습니다. 그리고 기존 문제와는 다르게 단순히 '정점 A에서 정점 B까지 최단 거리'나 '길이 이어져있는지 여부' 외에 플로이드 와샬 알고리즘을 수행하는 기준은 무궁무진하다는 점을 일깨워주는 좋은 문제였다고 생각합니다.

 

문제에서는 시작점에서 끝점으로 이동할 때, 양방향 도로가 몇 개가 필요한지 물어보았습니다.

따라서, 우리는 양방향 도로의 개수를 기준으로 그래프를 정의하고 플로이드 와샬 알고리즘을 수행한 후, 모든 정점에서 모든 정점에 대하여 최소한으로 필요한 양방향 도로의 개수를 구해야 합니다.

 

전반적인 로직은 다음과 같습니다.

 

 

1. 도로가 양방향이든 일방향이든 u에서 v까지는 무조건 갈 수 있으므로 비용은 0이다.

(여기서, 비용은 필요한 양방향 도로의 개수로 보면 됩니다.)

 

2. 만약, 도로가 일방향일 경우, v에서 u까지 가려면 양방향 도로를 하나 둬야 하므로 비용은 1이다.

 

3. 만약, 도로가 양방향일 경우, v에서 u까지 가는 데 비용은 0이다.

 

4. 위에서 정의한 배열을 플로이드 와샬 알고리즘을 수행한다.

 

 

위 설명을 예제를 통해 좀 더 알아봅시다.

 

 

예제

 

 

위와 같은 그래프가 있습니다. 먼저, 초기값을 세팅해 봅시다.

 

 

	1	2	3	4
1	0	0	INF	INF
2	1	0	0	INF
3	INF	0	0	0
4	INF	INF	1	0

 

 

문제에서 제시된 입력값만 가지고 초기값을 세팅하면 위의 표가 될 것입니다.

 

이제, 이를 플로이드 와샬 알고리즘을 통해 값을 확장시킵시다.

 

 

	1	2	3	4
1	0	0	0	0
2	1	0	0	0
3	1	0	0	0
4	2	1	1	0

 

 

위의 표는 시작점에서 끝점까지 갈 때 필요한 최소한의 양방향 도로의 개수입니다.

예를 들어, 4에서 1로 가려면 (1, 2)와 (3, 4)의 도로를 양방향으로 만들어주어야 하므로 양방향 도로의 개수는 2개가 필요하다는 식으로 이해하시면 되겠습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        int[][] arr = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    arr[i][j] = INF;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            arr[u][v] = 0; // u에서 v까지는 무조건 갈 수 있음.
 
            // (u, v) 도로가 일방향도로라면,
            // v에서 u까지 가려면 양방향도로가 설치되어야하므로
            // 비용을 1로 초기화한다.
            // (u, v) 도로가 양방향도로라면,
            // v에서 u까지 무조건 갈 수 있으므로
            // 비용은 0이다.
            arr[v][u] = (b == 0) ? 1 : 0;
        }
 
        // 플로이드 와샬 알고리즘 수행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) {
                        continue;
                    }
 
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
 
        int K = Integer.parseInt(br.readLine());
 
        StringBuilder sb = new StringBuilder();
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
 
            sb.append(arr[s][e] + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.