[BOJ] 11085 : Protest - travelbeeee

문제 : https://www.acmicpc.net/problem/11085

---

[ 주접주접 ]

 처음에는 DFS 탐색을 통해서 startNode에서 시작해서 탐색을 진행하며 경로 중 가장 작은 cost를 매개변수로 넘겨주며 endNode까지 탐색이 끝나면 답을 갱신하는 방법으로 알고리즘을 구현했다. 당연히, 시간 초과에 직면했고 그 후 갱신된 답보다 작거나 같은 경우에는 탐색을 중간에 종료하며 DFS 컷팅을 시도했으나 이 알고리즘도 시간 초과에 직면했다... 그러다 Union-Find 기법으로 문제를 해결할 수 있다는 글을 보았고 Union-Find로 A노드에서 B노드로 경로가 있는지 없는지 바로 체크할 수 있다는 점을 이용해서 문제를 해결했다.

 

[ 알고리즘풀이 ]

 우리는 startNode에서 endNode로 경로를 만들면되는데, 어차피 cost가 작은 간선보다는 cost가 큰 간선들로 경로를 만들고 싶다. 따라서, cost가 큰 간선부터 탐색하며 startNode와 endNode 가 경로가 생긴 순간 탐색을 종료하면 된다. 이때, startNode와 endNode가 경로가 생겼는지 안생겼는지는 Union-Find를 이용해서 쉽게 해결할 수 있다.

 

[ 예시 ]

1)

 cost가 가장 큰 간선 4 - 5 를 가지고와 4와 5를 Merge 합니다. 즉, 4번 5번 노드 사이에는 경로가 존재합니다. { 4, 5 }

2)

 다음으로 큰 간선인 5 - 6 을 가지고와 5 와 6을 Merge 합니다. { 4, 5, 6 } 이 한 집합이 되므로 4, 5, 6 사이에는 서로 경로가 존재합니다.

3)

 그 다음으로는 1 - 3 을 가지고와 1과 3을 Merge 합니다. { 1, 3 } / { 4, 5, 6 }

4)

 그 다음으로는 0 - 2 를 가지고와 0과 2를 Merge 합니다. { 0, 2 }  / { 1, 3 } / { 4, 5, 6 }

5)

 그 다음으로는 2 - 6을 가지고와 2와 6을 Merge 합니다. { 0, 2, 4, 5, 6 } / { 1, 3 }

6)

 그 다음으로는 1 - 2를 가지고와 1과 2를 Merge 합니다. { 0, 1, 2, 3, 4, 5, 6 }

이때, 3과 5가 같은 집합으로 합쳐졌으므로 3 - 5 사이에 경로가 존재하게 되므로 함수를 종료하면 됩니다.

#include<iostream>
#include<queue>

using namespace std;

int p, w, root[1000], startNode, endNode, x, y, z;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1);
	int pNum2 = find(num2);
	if (pNum1 != pNum2) {
		root[pNum1] = pNum2;
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> p >> w >> startNode >> endNode;
	for (int i = 0; i < p; i++)
		root[i] = i;

	priority_queue<pair<int, pair<int, int>>> q;
	for (int i = 0; i < w; i++) {
		cin >> x >> y >> z;
		q.push({ z, {x, y} });
	}
	while (!q.empty()) {
		pair<int, pair<int, int>> cur = q.top();
		q.pop();

		merge(cur.second.first, cur.second.second);

		if (find(startNode) == find(endNode)) {
			cout << cur.first << '\n';
			break;
		}
	}
	return 0;
}

---