[BOJ/Gold 3] 백준 11562 백양로 브레이크(C++)

문제 링크

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

11562번: 백양로 브레이크

 

 

문제

서울 소재 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줄에 걸쳐 이루어진다.

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

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

예제 입력 1

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

예제 출력 1

0
0
1
0
2
0
1

알고리즘 분류

• 최단 거리 알고리즘

풀이

M개의 길의 수를 입력받고 DP[U][V]를 0으로 초기화해준다. 그리고 C가 1이면 양방향 길이라는 뜻이므로 DP[V][U] 역시 0으로 초기화해준다. 하지만 C가 0이면 일방통행이라는 뜻이므로 DP[V][U]를 1로 초기화해준다. 이렇게 하면 플로이드-워셜을 통해 U에서 V로 가기 위해 필요한 양방향으로 바꿔줘야 하는 길의 개수를 구할 수 있게 된다.

건물의 개수가 최대 250개까지이므로 플로이드-워셜을 사용해서 O(n^3)의 시간복잡도를 가져도 시간이 초과되지 않는다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 251
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, U, V, C, B, K, S, E;
int DP[MAX][MAX];

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (i == j) {
                continue;
            }
            DP[i][j] = INF;
        }
    }
}

void settings() {
    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 (DP[i][j] > DP[i][k] + DP[k][j]) {
                    DP[i][j] = DP[i][k] + DP[k][j];
                }
            }
        }
    }
}

void find_Answer() {
    cout << DP[S][E] << "\n";
}

void input() {
    cin >> N >> M;
    while (M--) {
        cin >> U >> V >> C;
        DP[U][V] = 0;
        if (C == 1) {
            DP[V][U] = 0;
        }
        else {
            DP[V][U] = 1;
        }
    };
    settings();
    cin >> K;
    while (K--) {
        cin >> S >> E;
        find_Answer();
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}