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

문제

상근이는 매일 아침 실험실로 출근해서 샘플의 무게를 재는 일을 하고 있다. 상근이는 두 샘플을 고른 뒤, 저울을 이용해서 무게의 차이를 잰다.

교수님의 마음에 들기 위해서 매일 아침부터 무게를 재고 있지만, 가끔 교수님이 실험실에 들어와서 상근이에게 어떤 두 샘플의 무게의 차이를 물어보기도 한다. 이때, 상근이는 지금까지 잰 결과를 바탕으로 대답을 할 수도 있고, 못 할 수도 있다.

상근이는 결과를 출근한 첫 날부터 공책에 적어 두었다. 하지만, 엄청난 양의 무게가 적혀있기 때문에, 교수님의 질문에 재빨리 대답할 수가 없었다. 이런 상근이를 위해서 프로그램을 만들려고 한다.

상근이가 실험실에서 한 일이 순서대로 주어진다. 어떤 두 샘플의 무게의 차이를 구할 수 있는지 없는지를 알아내는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘: Union-Find

(1) (코드: 6~7)

 Union-Find 를 조금 변경했습니다.
 물체의 root를 저장하는 배열과 물체와 root 사이의 거리를 저장하는 배열을 만들어줍니다.

(2) (코드: 33~37)

우선 각 물체는 자신을 root로 두고, root까지 거리는 0 으로 초기설정합니다.

(3) (코드: 16~29) 

 '!' 입력으로 두 물체와 무게차 a, b, w 가 주어지면, a, b를 Union 합니다.
 a의 root를 aRoot, b의 root 를 bRoot 라고 하면, bRoot 의 root를 aRoot 로 바꾸어주고,
 aRoot와 bRoot 의 거리차를 dist[bRoot]에 저장 해줍니다.
 dist[bRoot] = (aRoot 기준 b 거리) - (bRoot 기준 b 거리)
 ( aRoot기준 b거리 = (aRoot기준 a거리) + (a기준 b 거리 ) )

(5) (코드: 9~15, 44~47) 

 i물체의 Find를 구현할 때, i물체와 root 간의 거리 dist[i]를 최신화 해줍니다.

(6) (코드: 48~51)

 '?' 입력으로 a,b 의 무게차를 출력을 할 때, a, b 가 같은 root이면 dist[b] - dist[a]를 , 다른 root 이면 UNKNOWN 을 출력해주면 됩니다.

Union-Find 를 적절히 변형하여 사용하는 것이 까다로운 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 100001;
	typedef long long ll;
	int N, M, Root[MAX];
	ll dist[MAX];
	// Find 변형
	int Update(int x){
	if(Root[x]==x) return x;
	int R = Update(Root[x]);
	// Root 까지 비용 업데이트
	dist[x] += dist[Root[x]];
	return Root[x] = R;
	}
	// Union 변형
	void merge(int a, int b, int diff){
	int aRoot = Root[a];
	int bRoot = Root[b];
	if(aRoot == bRoot) return;
	// aRoot 기준 b 의 위치
	int NewD = dist[a]+diff;
	// bRoot 기준 b 의 위치
	int OriginD = dist[b];
	// bRoot 를 aRoot 으로 재조정
	Root[bRoot] = aRoot;
	// 기존 bRoot 에서 aRoot의 거리
	dist[bRoot] = NewD - OriginD;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(1){
	cin >> N >> M;
	if(N==0&&M==0) break;
	for (int i = 1; i <= N; ++i){
	Root[i] = i;
	dist[i] = 0;
	}
	for (int i = 0; i < M; ++i){
	char ch;
	int a, b, w;
	cin >> ch >> a >> b;
	Update(a);
	Update(b);
	if(ch == '!'){
	cin >> w;
	merge(a,b,w);
	}
	else{
	if(Root[a]==Root[b]) cout << dist[b] - dist[a] << '\n';
	else cout << "UNKNOWN" << '\n';
	}
	}
	}
	return 0;
	}

view raw BOJ 3830.cpp hosted with ❤ by GitHub