[16562] 친구비

[HongyeongJu]

https://www.acmicpc.net/problem/16562
오늘 친구비라는 문제를 풀었는데.

• 정답코드

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

vector<int> parent;

struct Friend {
	int cost;
	int id;

	Friend(int id, int cost) {
		this->id = id;
		this->cost = cost;
	}
};

struct compare {
	bool operator()(Friend a, Friend b) {
		return a.cost > b.cost;
	}
};

int Find(int i) {
	if (parent[i] == i) return i;
	else {
		return parent[i] = Find(parent[i]);
	}
}

void Union(int a, int b) {
	int pa = Find(a);
	int pb = Find(b);

	if (pb > pa) {
		parent[pb] = pa;
	}
	else {
		parent[pa] = pb;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, M, K;

	cin >> N >> M >> K;

	parent = vector<int>(N + 1);
	priority_queue<Friend, vector<Friend>, compare> pq;
	set<int> s;
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;

		pq.push(Friend(i, num));
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		Union(a, b);
	}


	bool isOkay = false;
	int sum = 0;
	while (!pq.empty()) {
		Friend now = pq.top();
		pq.pop();

		//모두 연결이 되어있는가?
		bool isComplited = true;
		for (int i = 1; i <= N; i++) {
			if (Find(0) != Find(i)) {
				isComplited = false;
			}
		}

		if (isComplited) {
			isOkay = true;
			break;
		}

		// 연결 시도
		// 준석이는 0번이라고 생각하자
		// 연결이 안되어있으면
		if (Find(0) != Find(now.id)) {
			Union(0, Find(now.id));
			sum += now.cost;
		}
	}
	if (sum <= K) {
		cout << sum;
	}
	else {
		cout << "Oh no";
	}

	return 0;
}

• 오답코드

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

vector<int> parent;

struct Friend {
	int cost;
	int id;

	Friend(int id, int cost) {
		this->id = id;
		this->cost = cost;
	}
};

struct compare {
	bool operator()(Friend a, Friend b) {
		return a.cost > b.cost;
	}
};

int Find(int i) {
	if (parent[i] == i) return i;
	else {
		return parent[i] = Find(parent[i]);
	}
}

void Union(int a, int b) {
	int pa = Find(a);
	int pb = Find(b);

	if (pb > pa) {
		parent[pb] = pa;
	}
	else {
		parent[pa] = pb;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, M, K;

	cin >> N >> M >> K;

	parent = vector<int>(N + 1);
	priority_queue<Friend, vector<Friend>, compare> pq;
	set<int> s;
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;
		
		pq.push(Friend(i, num));
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		Union(a, b);
	}


	bool isOkay = false;
	int sum = 0;
	while (!pq.empty()) {
		Friend now = pq.top();
		pq.pop();

		//모두 연결이 되어있는가?
		bool isComplited = true;
		for (int i = 1; i <= N; i++) {
			if (Find(0) != Find(i)) {
				isComplited = false;
			}
		}

		if (isComplited) {
			isOkay = true;
			break;
		}


		// 연결 시도
		// 준석이는 0번이라고 생각하자
		// 연결이 안되어있으면
		if (Find(0) != Find(now.id)) {
			// 만약 비용이 
			if (K >= now.cost) {
				sum += now.cost;
				K -= now.cost;
				Union(0, Find(now.id));
			}
			else {
				break;
			}
		}
	}
	if (isOkay) {
		cout << sum << "\n";
	}
	else {
		cout << "Oh no" << "\n";
	}

	return 0;
}

위의 코드는 정답이 되는데, 아래의 코드는 정답이 안되네요.. 제가 보기엔 별차이 없어보이고 왜 그런지 잘 모르겠습니다.. 고수분들 도와주세요 ㅠㅠ..

[YeonsangYoon]

일단 아래 코드 디버깅을 좀 해봤는데 문제점을 찾기 힘드네요
문제 접근을 굉장히 Naive하게 하셨네요.

void Union(int a, int b) {
	int pa = Find(a);
	int pb = Find(b);

	if (pb > pa) {
		parent[pb] = pa;
	}
	else {
		parent[pa] = pb;
	}
}

유니온 구현 부분에서 pa와 pb가 같을 경우를 고려하시는 게 좋을 것 같아요.

void Union(int a, int b) {
	int pa = Find(a);
	int pb = Find(b);

	if(pa == pb) return;
        else if(pa > pb) swap(pa, pb);
        parent[pb] = pa;
}

이렇게 하면 굳이 union을 호출하기 전에 find(a) != find(b)를 검사할 필요 없이 자동적으로 해결해줍니다.

일단 저는 문제 접근을 Union부분에서 차이점을 뒀습니다.
m개의 친구 관계를 통해 union을 하게 되면 총 n명의 사람들 내에서 여러 개의 트리가 생성될 것입니다.
그러면 저희가 구하고자 하는 답은 모든 사람을 다 친구로 만드는 최소 비용이기 때문에...
결국 생성된 트리 내에서 최소 친구비를 골라서 합하는 것을 목표로 해야합니다.

예를 들어 m번의 union으로 다음과 같은 트리가 형성되었다고 생각해보죠.

결국 각 트리 내에서의 최소 비용만을 선택하는 것이 정답일 것입니다.
그러면 어떻게 트리 내에서 최소 비용을 빠른 시간 복잡도로 찾을 것인가? 에 대한 해결이 필요하죠.
저는 이걸 Union by Rank에서 착안해서 Union by payment 방식으로 해결했습니다.

위 그림처럼 Union을 할 때 어떤 트리 루트의 비용이 작은 트리에 큰 트리를 집어넣으면 항상 트리의 루트가 가장 작은 값을 유지합니다.
그럼 결국 최소비용을 계산하는 과정에서 트리 전체를 탐색할 필요 없이 해당 트리의 루트 값만 확인하면 되는 것입니다.

이렇게 구현한 제 코드는 아래와 같습니다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int n, m, k;

struct DisJointSet {
	int parent[10001];
	int payment[10001];
	bool isRoot[10001];

	void init(int n) {
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
			isRoot[i] = true;
			cin >> payment[i];
		}
	}
	int find(int n) {
		if (parent[n] == n) return n;
		return parent[n] = find(parent[n]);
	}
	void merge(int a, int b) {
		int pa = find(a);
		int pb = find(b);

		if (pa == pb) return;
		else if (payment[pa] > payment[pb]) swap(pa, pb);

		parent[pb] = pa;
		isRoot[pb] = false;
	}
	int get_min_payment() {
		int retval = 0;
		for (int i = 1; i <= n; i++) {
			if (isRoot[i])
				retval += payment[i];
		}
		return retval;
	}
};
DisJointSet dsu;

int main(void) {
	fastio;

	cin >> n >> m >> k;

	dsu.init(n);

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		dsu.merge(a, b);
	}

	int ans = dsu.get_min_payment();

	if (ans > k)
		cout << "Oh no";
	else
		cout << ans;

}

[HongyeongJu]

연상님 감사합니다!!
코드를 보니 "이런식으로 구현할 수 있구나!"라고 무릎을 탁치고 깨우치게 되었습니다!
저는 단순하게 Union-Find 개념만 사용하였는데, Union by Payment나 isRoot 플래그를 사용해서 각 루트의 합을 구하는 것까지.
좋은 기법인 것 같아요! 한 수 배워갑니다 ! 감사합니다.

[YeonsangYoon]

영주님 위 코드 시간복잡도가 최악의 경우 O(N^2logN)인데 성공하는 걸 보고 혹시 완전 탐색으로 구현해도 성공하는 지 확인해봤는데
성공하네요 ㅋㅋ

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int n, m, k;
int payment[10010];
bool visited[10010];
vector<int> adjlist[10010];

void _input() {
	cin >> n >> m >> k;
	
	for (int i = 1; i <= n; i++) {
		cin >> payment[i];
		visited[i] = false;
	}

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
}

int dfs(int node) {
	int retval = payment[node];
	visited[node] = true;

	for (int& next : adjlist[node]) {
		if (visited[next])
			continue;
		retval = min(retval, dfs(next));
	}

	return retval;
}

int main(void) {
	fastio;

	_input();

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			ans += dfs(i);
		}
	}

	if (ans > k)
		cout << "Oh no";
	else
		cout << ans;
}

빨강이 Union find 파랑이 dfs인데 심지어 걸린 시간이 같네요 ㅋㅋㅋ 문제 조건을 보면 n이 10000이라 가능한 풀이 같습니다!