BOJ3830 교수님은 기다리지 않는다

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

1번부터 N번까지의 샘플에 대해

두 샘플의 무게 차이 정보가 주어질 때

교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고

구할 수 없으면 UNKNOWN을 출력한다

 

 

 

Disjoint Set

Union & Find를 이용하는 문제인데 edge에 cost가 있다.

 

분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다.

scanf,printf보다 cin,cout이 훨씬 빠르고 편했다.

 

---

par[N]  N개 샘플의 부모 (set number)

w[N]    N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게)

 

 

 

! a b c

: b가 a보다 c그램 무겁다.

 

a와 b를 union한다.

1. a,b의 부모 para,parb를 구한다.

2. 값이 더 작은 부모로 union한다. 이때 부모 간 무게 차이를 계산해줘야 함.

2-1. para로 union하는 경우

w[a]는 w[para]를 기준으로,

w[b]는 w[parb]를 기준으로 계산된 상태.

b가 a보다 c그램 더 무겁기 때문에, parb와 para를 union하면 w[b]=w[a]+c가 되어야 한다.

따라서 w[parb]에 b의 새로운 무게(w[a]+c)와 현재 무게(w[b])의 차를 더해줘야 한다.

2-2. parb로 union하는 경우

반대로 w[para]에 a의 새로운 무게(w[b]-c)와 현재 무게(w[a])의 차를 더한다.

if (q == '!') {
	cin >> c;

	if (para < parb) w[parb] += (w[a] + c - w[b]), par[parb] = para;
	else w[para] += (w[b] - c - w[a]), par[para] = parb;
}

 

그림을 보면 더 이해가 빠를 듯

 

 

 

? a b

: b가 a보다 몇 그램 무거운가?

 

위 그림과 같은 상황에서 a=2, b=3이라면

두 vertex의 부모가 모두 1인데도 당장의 par[2]와 par[3]은 다른 상태이다.

당연히 무게도 다른 기준으로 계산된 상태이므로

Find에서 부모를 업데이트하면서 무게도 같이 계산한다.

 

Find(2)의 경우 line3에서 종료된다.

Find(3)의 경우 원래 부모인 2의 무게를 3의 무게에 더해줘야 한다. 

3의 무게는 2의 무게를 0으로 할 때의 값, 2의 무게는 1의 무게를 0으로 할 때의 값

즉 현재 cur의 무게는 old_par를 기준으로 계산한 값이고

old_par의 무게는 new_par을 기준으로 계산한 값이니까

int Find(int cur) {
	int old_par = par[cur];
	if (par[old_par] == old_par) return old_par;

	int new_par = Find(old_par);
	w[cur] += w[old_par];
	par[cur] = new_par;
	return new_par;
}

 

---

이런 예시를 생각해서 여러 번 돌려봤다

 

 

 

먼저 쿼리 종류와 a, b부터 입력받고 a, b의 부모 para, parb를 찾는다.

쿼리가 !라면 두 재료의 무게 차 c를 입력받고 union

쿼리가 ?라면 para, parb 비교 결과에 따른 출력

#include <iostream>
#include <queue>
using namespace std;

int w[100001];
int par[100001];

int Find(int cur) {
	int old_par = par[cur];
	if (par[old_par] == old_par) return old_par;

	int new_par = Find(old_par);
	w[cur] += w[old_par];
	par[cur] = new_par;
	return new_par;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int N, M, a, b, c;
	char q;

	while (1) {
		cin >> N >> M;
		if (!N) return 0;
		for (int i = 1; i <= N; ++i) par[i] = i, w[i] = 0;
		
		while (M--) {
			cin >> q >> a >> b;
			int para = Find(a);
			int parb = Find(b);

			if (q == '!') {
				cin >> c;

				if (para < parb) w[parb] += (w[a] + c - w[b]), par[parb] = para;
				else w[para] += (w[b] - c - w[a]), par[para] = parb;
			}
			else{
				if (para != parb) cout << "UNKNOWN\n";
				else cout << w[b] - w[a] << "\n";
			}
		}
	}
}