BOJ 11562 백양로 브레이크

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

11562번: 백양로 브레이크

 

단방향 그래프가 주어지고 $M$개의 $u, v$가 주어질 때, 몇 개의 단방향 길을 양방향 길로 바꿔야 $u$에서 $v$로 갈 수 있는지 출력하는 문제입니다.

 

플로이드-워셜을 응용하면 해결할 수 있습니다. 단방향 간선의 경우 해당 방향으로 이동할 때는 바꿔야 하는 길이 없으므로 코스트가 0이라고 할 수 있습니다. 단방향 간선의 반대 방향의 경우 해당 방향으로 이동하려면 길을 하나 바꿔야 함으로 코스트가 1이라고 할 수 있습니다. 이렇게 초기 그래프를 구성한 뒤, 플로이드-워셜 알고리즘을 수행하면 모든 정점 쌍에 대해 바꿔야 하는 길의 갯수를 알 수 있습니다.

 

처음에 플로이드-워셜을 양방향과 단방향 간선 두 경우에 대한 풀이로 접근했다가 틀리고, 우선순위 큐를 쓰는 풀이로 접근했다가 틀리고, 다시 플로이드-워셜을 사용하는 풀이로 AC를 받았습니다. 플로이드-워셜을 응용하는 문제라는 것을 알아채는 것이 이 문제에 어려운 점이라고 생각합니다. 기여를 보니 우선순위 큐를 사용하는 풀이도 있는 것 같은데, 아직 잘 모르겠습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

const int INF = 0x3f3f3f3f;

using namespace std;

int T, n, m, k, dist[300][300];

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = INF;
                if (i == j) dist[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i++) {
            int x, a, b;
            cin >> a >> b >> x;
            dist[a][b] = 0;
            if (x) dist[b][a] = 0;
            else dist[b][a] = 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

        cin >> k;

        while (k--) {
            int u, v;
            cin >> u >> v;

            cout << dist[u][v] << endl;
        }
    }

    return 0;
}