[종만북] 문제: TPATH
서론
문제 설명
$G = (V, E)$에서, 각 Vertex를 $v_i$라 할 때, $v_0$부터 $v_{n-1}$까지의 path들 중, path를 이루는 edge의 최대/최소 weight 차이의 최솟값을 구하시오.
문제 유형
최소 범위 경로(Minimum Range Path) 문제를 풀어봅시다.
최소 범위 경로란?
최소 범위 경로 문제는 그래프에서 두 정점사이를 연결하는 경로들 중에서, 경로를 구성하는 간선들의 가중치 중 최대값과 최소값의 차이가 최소가 되는 경로를 찾는 문제입니다.
어떤 식으로 접근해야 할까?
이 문제는 단순히 DFS/BFS적인 접근으로 풀려고 하면 엄청 힘듭니다.
이런 문제를 풀 때에는 조금 다른 접근이 필요한데, 조금 더 쉬운 문제로 변환해보는 것입니다.
우리가 사용할 수 있는 edge들의 weight의 하한을 미리 정해두고 계산해보는 방식은 어떨까요? 그러면 weight의 상한을 조절해가면서, 경로가 존재할 수 있는 상한의 최솟값을 구하면 되겠네요.
이것을 모든 edge에 대해 하한을 미리 정해두고, 각 경우에 대해 상한을 계산하는 식으로 알고리즘을 짜면 되겠습니다!
brute-force
무식하게 한번 구현해볼까요..? 모든 하한과 상한을 아예 정해버리고, 이 하한과 상한이 정해져 있을 때 path가 존재하는지 여부를 검사하고 최솟값을 갱신하는 알고리즘을 구상한다고 쳐봅시다.
path가 존재하는지 여부를 검사하는건, BFS로 하면 되겠네요. 그러면 시간복잡도는 $O(n)$입니다.
BFS를 $O(n^2)$번 수행하므로 이 알고리즘의 시간복잡도는 $O(n^3)$임을 알 수 있습니다… 쓰면 안되겠네요.
여기서 우리는 최적화를 사용할 수 있습니다. 최적화하는 방식은 다음과 같습니다.
- 하한을 정하고 상한을 찾을 때, 이분 탐색을 이용하여 찾습니다.
- MST를 만드는 알고리즘을 응용해서 path를 만들며 최솟값을 갱신합니다.
- brute-force방식을 최적화합니다.
한번 2번 방식으로 풀어봅시다!
MST 알고리즘 변형
MST를 만드는 알고리즘을 응용해서 path를 만들 수 있을까요?
MST를 만드는 알고리즘의 공통점은, 결국 edge후보들 중 weight가 가장 적은 것부터 추가해나간다는 것입니다.
그렇다면, 계속 추가해나가다가, path가 존재하는 시점에서의 weight의 최대/최소의 차이를 찾을 수 있겠습니다.
알고리즘 구상
알고리즘 설계
- edge를 정렬합니다.
- 각 edge에 대해 오름차순으로, edge의 하한을 정합니다.
- Kruscal’s algorithm을 이용해서 edge를 추가하면서 경로가 존재하는지 판단합니다. 만약 경로가 판단 시, 이때의 최대/최소 차이를 구합니다.
- 2, 3 을 반복하며 최솟값을 갱신합니다.
시간 복잡도
$|E| = n$으로 정의하면,
edge를 정렬하는데 $O(n \log n)$시간,
각 edge에 대해 Kruscal’s algorithm을 수행하므로 $O(n^2 \times \alpha(n))$시간이 걸립니다.
알고리즘 구현
helper 함수(Union-find)
Kruscal’s algorithm을 도와주는 Union-find 함수입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int parent[2000], r[2000];
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (r[x] > r[y])
parent[y] = x;
else {
parent[x] = y;
if (r[x] == r[y]) r[y]++;
}
}
main()
앞서 정의한 Union-find를 이용해 하한을 미리 정하면서 Kruscal로 MST를 생성, path를 찾으며 최솟값을 갱신하는 함수입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main() {
fastIO;
int c;
cin >> c;
while (c--) {
cin >> n >> m;
edge.clear();
int a, b, c;
while (m--) {
cin >> a >> b >> c;
edge.push_back(make_pair(c, make_pair(b, a)));
}
sort(edge.begin(), edge.end());
int answer = INF;
for (int i = 0; i < edge.size(); i++) {
iota(parent, parent + n, 0);
memset(r, 0, n * sizeof(r[0]));
int min = INF;
int lo = edge[i].first;
for (int j = i; j < edge.size(); j++) {
merge(edge[j].second.first, edge[j].second.second);
if (find(0) == find(n - 1)) {
min = edge[j].first - lo;
break;
}
}
answer = answer < min ? answer : min;
}
cout << answer << "\n";
}
return 0;
}
최종 코드
여기에서 확인하세요!