(백준 16562번 친구비 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 3

백준 16562번

https://www.acmicpc.net/problem/16562

 

유니온 파인드 문제인 걸 알고봐서 아이디어를 내는 건 어렵지 않았다.

연결된 그래프 중 가장 친구비가 작은 노드를 root node로 지정하고, root node들을 다 더한 값이 이준석 학생이 가진 돈보다 많으면 된다도 생각했다.

 

고런데,,,!! 29%에서 안되는 것이 아닌가!

 

그래서 찾은 문제점 1. 

 

일단 반례부터 투척

(출처) : https://www.acmicpc.net/board/view/81875

반례 :

5 3 20

10 20 20 10 30

1 3

2 4

5 4

답 : 20

 

따따봉 👍🏻

 

node의 번호와 node의 value는 다르다. 1번이라고 해서 무조건 작은 친구비를 갖는게 아님!!!!

 

위 반례를 통해 그 부분을 수정할 수 있었다.

 

 문제점 2. 

_union 함수 내부에서 root node를 정해줄 때 value가  작은 node가 root node가 되도록 지정해주지 않았다.

무지성 p[a] = b를 외친 덕분에 디버깅을 하기 아주 어려웠다는...^_^

 

이 부분은 과거의 내 코드를 보면서 깨달았다.

 

그렇게 작성한 코드

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

constexpr int MAX_N = 10000 + 1;
int value[MAX_N];
int p[MAX_N];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

// a의 부모노드가 b
void _union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	// ★ 여기가 틀린 지점
	if (value[a] < value[b]) p[b] = a;
	else p[a] = b;
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M, K; cin >> N >> M >> K;
	fill_n(p, N+1, -1);

	for (int i = 1; i <= N; i++) {
		int temp; cin >> temp;
		value[i] = temp;
	}
	if( M != 0){
		for (int i = 0; i < M; i++) {
			int v, w; cin >> v >> w;
			if (v == w) continue;
			if (value[v] > value[w]) _union(v, w);
			else if (value[v] < value[w])_union(w, v);
			else {
				if (v > w) _union(v, w);
				else _union(w, v);
			}
		}
	}
	
	int money = 0;
	for (int i = 1; i <= N; i++) {
		if (p[i] == -1) money += value[i];
	}

	if (money > K) cout << "Oh no";
	else cout << money;
	return 0;
}