[백준 11562] 백양로 브레이크 (C++)

이 문제는 길 정보가 주어졌을 때, s에서 e까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야만 하는지를 구하는 문제이다.

나는 처음에 브루트포스로 풀 수 있는지 고려해봤다. 최악의 경우는 모든 길이 단방향으로 주어진 경우이므로 최대 $\frac {250 \times 249} {2} = 31,125$개를 뒤집어야 하므로 $\sum_{k = 0} ^ {n} {_nC_k} = 2^n$가지가 가능하며, 이는 $2^{31,125}$가지이다. 따라서, 브루트포스로는 절대 풀 수 없다.

다음으로 고려한 것은 주어진 그래프에서 s에서 e로 방문하려면, 간선의 방향을 바꿔야하는 횟수를 구해보기로 했다. 시작 정점과 도착 정점으로 총 2개의 정보가 필요하므로 2차원 배열 형태로 나타날 것임을 유의해서 표현해야한다.

예제 입력에 대한, 간선의 방향을 바꿔야하는 횟수를 구해보도록 하자.

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

이러한 예제 입력이 주어질 때, 우리는 첫번째 줄의 n, m과 두번째 줄부터 m+1개의 줄에 걸쳐 주어지는 u, v, b를 통해 다음과 같이 방향 변환 횟수인 행렬 w가 표현된다.

$w = \begin{pmatrix} 0 & 0 & \infty & \infty \\ 1 & 0 & 0 & \infty \\ \infty & 0 & 0 & 0 \\ \infty & \infty & 1 & 0 \end{pmatrix}$

좀 더 구체적으로 설명하자면, 먼저 자기 자신으로는 방향을 바꾸지 않아도 도달할 수 있음이 자명하므로 $[1, n]$범위의 임의의 $i$에 대해서 w[i][i] = 0가 성립한다.

그리고, 1 2 0이므로 단방향 통행만 가능하므로 반대 방향은 해당 길을 양방향으로 변경해야 통행이 가능함이 자명하다. 따라서, w[1][2] = 0, w[2][1] = 1가 된다.

2 3 1은 양방향 통행이 가능하므로 길을 바꾸지 않아도 서로 통행이 가능함이 자명하다. 따라서, w[2][3] = 0, w[3][2] = 0이 된다.

3 4 0도 역시 단방향 통행만 가능하므로 반대 방향은 해당 길을 양방향으로 변경해야 통행이 가능하다. 따라서, w[3][4] = 0, w[4][3] = 1이 된다.

나머지 관계는 입력만으로 알 수 없어 $\infty$로 표현했다.

이때, 문제 조건에서 "출발지와 도착지를 입력하면 도착지까지 가기 위해 최소 몇 개의 길을 양방향으로 바꿔야만 하는지" 구해야한다고 언급하고 있다. 따라서, 이 문제를 방향을 변경해야되는 길을 최소한으로 이용하면서 목적지에 도달해야하는 문제로 인식할 수 있다. 즉, 길을 양방향으로 변경하는 것을 비용이라 생각했을 때, 두 정점간의 최단 거리를 구하는 문제가 된다. 이는, 플로이드 워셜로 접근할 수 있음을 시사한다.

우리는 위에서 구한 2차원 배열 w에서 플로이드 워셜 알고리즘을 수행하면 되는 것을 알아냈다. 이를 수행한 결과를 나타내면 다음과 같다.

$w = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 \end{pmatrix}$

따라서, 쿼리로 s, e가 주어지면, 우리는 w[s][e]를 출력하면 끝임을 알 수 있다.

이제 시간 복잡도를 고려해보자. 입력은 $O(N + M)$, 플로이드 워셜은 $O(N^3)$, 쿼리에 대한 출력을 하는 부분은 $O(K)$가 되므로 전체 시간 복잡도는 $O(N^3)$으로 시간 내에 문제를 해결할 수 있다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000;
int n, m;
int w[251][251];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		fill(w[i], w[i] + n + 1, INF);
		w[i][i] = 0;
	}
	while (m--) {
		int u, v, b;
		cin >> u >> v >> b;
		w[u][v] = min(w[u][v], 0);
		w[v][u] = min(w[v][u], 1 - b);
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
			}
		}
	}

	int k;
	cin >> k;
	while (k--) {
		int s, e;
		cin >> s >> e;
		cout << w[s][e] << "\n";
	}
}