[BOJ 6135] Cow Hurdles

2021년 5월 4일

문제는 여기서 풀 수 있습니다.

문제 요약

$N$ 개의 정점으로 이루어진 가중치가 있는 방향 그래프가 주어집니다. 그 뒤 $a$ 와 $b$ 로 이뤄진 $Q$ 개의 쿼리가 주어집니다.

각 쿼리에 대해서 $a$ 에서 $b$ 로 가는 경로 중 마주치는 간선들의 가중치 중 가장 큰 값이 가장 작게 만드는 경로를 찾아야 합니다. 만약 $a$ 에서 $b$ 로 가는 경로가 없다면 -1을 출력합니다.

문제 풀이

$D[a][b]$ 를 쿼리 $a$ , $b$ 의 값이라고 합시다. 이때 $D[a][b]$ 는 $a$ 에서 $b$ 로 가는 경로에 있는 임의의 정점 $k$ 를 기준으로 $D[a][k]$ 와 $D[k][b]$ 두 개의 부분 문제로 나눌 수 있고 부분 문제들의 답을 이용해 원래 문제의 답을 구할 수 있습니다. $D[a][k]$ 와 $D[k][b]$ 중 큰 값이 $D[a][b]$ 의 후보가 됩니다. $k$ 는 모든 정점이 될 수 있기 때문에 모든 정점에 대해 $D[a][b]$ 의 값이 될 수 있는 후보를 찾고 그중 가장 작은 값을 선택하면 $D[a][b]$ 의 값을 구할 수 있습니다.

이러한 과정은 플로이드-워셜 알고리즘과 매우 흡사합니다. 따라서 시간 복잡도는 $O(N^3)$ 이지만 N이 최대 300이므로 충분히 빠른시간내에 문제를 해결할 수 있습니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>

const int INF = 987654321;
int n, m, t, u, v, w, A[310][310];

int main() {
	scanf("%d%d%d", &n, &m, &t);

	for (int i = 1 ; i <= n ; ++i) {
		for (int j = 1 ; j <= n ; ++j) {
			A[i][j] = i == j ? 0 : INF;
		}
	}

	while (m--) {
		scanf("%d%d%d", &u, &v, &w);
		A[u][v] = w;
	}

	for (int k = 1 ; k <= n ; ++k) {
		for (int i = 1 ; i <= n ; ++i) {
			for (int j = 1 ; j <= n ; ++j) {
				if (A[i][k] != INF && A[k][j] != INF) {
					A[i][j] = std::min(A[i][j], std::max(A[i][k], A[k][j]));
				}
			}
		}
	}

	while (t--) {
		scanf("%d%d", &u, &v);
		printf("%d\n", A[u][v] == INF ? -1 : A[u][v]);
	}
}