백준 16562번 친구비(C++)

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

16562번: 친구비

 

문제 해석을 잘못해서 어렵게 생각하고 있었다. 친구의 친구는 친구라고 해서 인접한 관계만 가능하고 한 칸 이상 떨어지면 안되는 것이라고 생각했다. 그래서 트리에서 다이나믹 프로그래밍을 진행했는데 정답이 아니었다..!! 이 문제는 유니온 파인드였다. 맨 처음 생각난 건 유니온 파인드였는데 문제 해석을 잘못했다.

 

결국 구해야하는 것은 각 그래프마다 가장 작은 값을 찾는 것이다. 

 

그러므로 풀이법은 두가지다.

 

1. dfs, bfs

 

그냥 N개의 노드를 모두 도는 방법이다. 가장 간단하다.

 

2. 유니온 파인드

 

유니온 파인드를 통해, 친구비가 싼 노드의 번호로 묶어 마지막에 조상을 찾아 내는 방법 일반적인 유니온 파인드에서 조금만 코드를 수정하면 된다. 항상 유니온 파인드는 그저 부모가 작거나 큰 값으로 부모설정하는 것이 일반적이었는데 이렇게 무언가의 조건에 따라 부모를 결정하는 것을 배웠다.

 

먼저 dfs 사용한 코드

 

#include <iostream>
#include <vector>
#include <map>

#define MAX 10001
#define INF 10000000

using namespace std;

map<int, int> friendCost;
vector<int> node[MAX];

bool visited[MAX] = { false, };
int N, M, K;
int MinValue = INF;

void dfs(int now_node) {
	MinValue = min(MinValue, friendCost[now_node]);

	for (int i = 0; i < node[now_node].size(); i++) {
		int nextNode = node[now_node][i];
		if (visited[nextNode] == false) {
			visited[nextNode] = true;
			dfs(nextNode);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		int cost;
		cin >> cost;

		friendCost.insert({ i + 1, cost });
	}

	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		node[s].push_back(e);
		node[e].push_back(s);
	}

	int allCost = 0;

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) { 
			visited[i] = true;
			dfs(i);

			allCost += MinValue;
			MinValue = INF;
		}
	}

	if (allCost <= K) cout << allCost << '\n';
	else cout << "Oh no" << '\n';
}

 

 

다음은 유니온파인드 코드

 

#include <iostream>
#include <map>
#define MAX 10001
using namespace std;
map<int, int> friendCost;
int parants[MAX];

int find(int n) {
	if (parants[n] == n) return n;
	else return parants[n] = find(parants[n]);
}

void merge(int a, int b) {
	int pa = find(a);
	int pb = find(b);

	if (friendCost[pa] < friendCost[pb]) parants[pb] = parants[pa];
	else parants[pa] = parants[pb];
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N, M, K;
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		int cost;
		cin >> cost;
		friendCost.insert({ i + 1, cost });
		parants[i + 1] = i + 1;
	}

	for (int i = 0; i < M; i++) {
		int s, t;
		cin >> s >> t;

		merge(s, t);
	}
	bool visited[MAX] = { false, };

	int AllCost = 0;

	for (int i = 1; i <= N; i++) {
		int pi = find(i);

		if (visited[pi] == false) {
			AllCost += friendCost[pi];
			visited[pi] = true;
		}
	}

	if (AllCost <= K) cout << AllCost << '\n';
	else cout << "Oh no" << '\n';}

 

 

유니온 파인드가 조금 더 빠르다.