백준 No.3830 [교수님은 기다리지 않는다]

Baekjoon Online Judge No.3830 [교수님은 기다리지 않는다]

---

  문제 

3830번: 교수님은 기다리지 않는다 (acmicpc.net)

3830번: 교수님은 기다리지 않는다

---

  설명 

  유니온 파인드 (2021.08.06 - 유니온 파인드 (Union Find, Disjoint set))알고리즘을 이용하여 샘플(노드)을 추가해야 하는 경우엔 추가하고 두 샘플의 무게를 비교할 땐 비교를 해야한다. 유니온 파인드 알고리즘은 노드들간의 그룹 여부를 알 수 있는 알고리즘 이다. 하지만 이 문제에선 '샘플의 무게'라는 데이터가 추가적으로 요구가 되므로, 유니온 파인드를 통한 노드들의 트리(그룹) 구성 및 해다아 트리의 노드들간의 관계를 파악해야 한다.

 

  기존 유니온 파인드 알고리즘에 대한 함수에서, long long date type 의 weight 배열을 추가 선언을 해 주었다. weight[k]는 k'th 노드와 parent[k] 노드의 무게차이를 저장한다. 임의의 노드의 부모 노드 및 루트 노드는 데이터가 계속해서 추가됨에따라 변경될 수 있다. 그 때 마다 weight[k]는 최대한 루트 노드와 값이 비교가 되도록 parent[k]를 계속해서 루트 노드로 업데이트를 해준다.

 

  루트 노드가 업데이트 되었을 때 기존의 루트 노드에 해당되는 weight 배열을 업데이트 해야한다. 이전에는 본인이 루트 노드였으니 weight[ ] 의 값은 0 이었으나, 이제 루트 노드가 새로 생겼으니 새로 생긴 루트 노드와의 무게 차이를 weight[ ] 에 업데이트를 한다.

 

! 1 2 100 ! 2 3 100 ! 4 3 150

  이와 같은 입력에 대해서 유니온 파인드로 구성되는 트리 및 parent, weight 배열의 값들은 이와 같이 변한다.

0123

  Union function 

void Union(int a, int b, int w) {
	int ra = find(a);
	int rb = find(b);

	if (ra == rb) return;

	weight[rb] = weight[a] - weight[b] + w;
	parent[rb] = ra;
}

  Union 함수는 b'th 노드가 a'th 노드보다 w 만큼 무거운 경우에 대한 유니온 함수이다.

 

  이와 같은 경우에서 8번째 샘플이 4번째 샘플보다 k 만큼 무겁다고 데이터가 들어왔다고 하자. 두 트리의 샘플(노드)끼리 비교를 하는 상황인 경우에는 결국 weigth[4] 에는 4번째 샘플과 1번째 샘플의 무게 차, weight[8] 에는 8번째 샘플과 6번째 샘플의 무게 차 값이 저장되어 있으므로  이 세 데이터를 통해 1번째 샘플과 6번째 샘플의 관계를 알 수 있다. 

 

 

  4'th 노드의 루트 노드인 1'th 노드가 8'th 의 루트 노드인 6'th 노드의 루트 노드가 되었고, weight[6] 의 값은 weight[4] - weight[8] + 10으로 초기화가 되었다. 이러한 방식으로 Union 함수가 구현이 되었다.

 

  Find function 

int find(int cur) {
	if (parent[cur] == cur) return cur;
	else {
		int curParent = find(parent[cur]);
		weight[cur] += weight[parent[cur]]; 
		return parent[cur] = curParent;
	}
}

  Find 함수는 입력으로 들어온 노드의 루트 노드를 리턴한다. 또한 부모 노드의 부모 노드를 계속해서 탐색하여 루트 노드에 도달하면서, weight 배열도 업데이트를 해 준다.  재귀를 통해 처음에 입력된 노드의 루트 노드까지 이동을 한 후 그 때 부터 그 노드의 parent값과 weight 값을 계속해서 업데이트를 하고, 최종적으론 처음에 입력된 노드의 parent 값과 weight 값이 업데이트가 된다. 아래 Find(5) 를 할 때 노드들의 parent 값의 업데이트를 표현 해 보았다.

 

Find (5) 과정

---

 

  Code 

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001

using namespace std;
typedef long long ll;

int parent[MAX];
ll weight[MAX];
int n, m;

int find(int cur) {
	if (parent[cur] == cur) return cur;
	else {
		int curParent = find(parent[cur]);
		weight[cur] += weight[parent[cur]]; 
		return parent[cur] = curParent;
	}
}

void Union(int a, int b, int w) {
	int ra = find(a);
	int rb = find(b);

	if (ra == rb) return;

	weight[rb] = weight[a] - weight[b] + w;
	parent[rb] = ra;
}

void init() {
	cin >> n >> m;

	memset(weight, 0, sizeof(weight));

	for (int i = 1; i <= n; i++)
		parent[i] = i;
}

void solve() {
	char c;
	int a, b, w;

	init();

	while (n || m) {
		while (m--) {
			cin >> c;

			if (c == '!') { // merge
				cin >> a >> b >> w;
				Union(a, b, w);
			}
			else if (c == '?') { // calculate weight
				cin >> a >> b;

				if (find(a) != find(b)) cout << "UNKNOWN\n";
				else cout << weight[b] - weight[a] << '\n';
			}
		}
		init();
	}
}


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

	solve();
}