[BOJ] 백준 20927. Degree Bounded Minimum Spanning Tree (Gold I)

문제는 아래와 같다.

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

20927번: Degree Bounded Minimum Spanning Tree

즉, 요약하자면 평범한 MST 문제이나, 차수 제한까지 포함된 MST를 만들어보란 소리이다.

처음엔 되게 간단한 MST 문제인 줄 알았으나.., 알고보니 NP-Complete 문제였다.

---

시행착오 및 해설

처음에는 일반적인 mst문제처럼 해결해되, 차수 제한을 뛰어넘게 될 경우 continue하는 방법으로 접근하였다.

그러나 자꾸 42%에서 틀림을 확인하였다.

https://www.acmicpc.net/board/view/69321

글 읽기 - 유니온파인드 이용 42%에서 틀리는데 어디가 문젤까요?

바로 아래와 같은 테스트케이스 때문이다.

7 12
1 2 1 2 2 2 2
1 2 8
1 4 4
1 7 1
2 4 55
2 7 10
2 3 7
2 6 3
6 7 21
3 6 30
4 5 4
3 5 50
6 5 100

YES
1 7
2 4
2 6
6 7
4 5
3 5

위 코드와 같이 작성하면 NO가 나올 것이다.

왜냐 하면, mst 풀이는 무조건 비용이 작은 것부터 연결하다보니 모든 경우를 탐색하는 것이 아니기 때문이다.

위 테스트케이스같은 경우엔, 비용이 다소 크더라도 모두 연결할 수 있는 경우와, 비용이 작은 순부터 연결하면 대부분은 연결되나 일부가 연결이 안되는 경우가 모두 존재한다. 비용이 작은순부터 연결하다보니 후자의 경우만 탐색하는 것이다.

 

차수와 비용을 모두 고려하여 트리를 만들어야 하므로 브루트포스로 접근해야 한다.

dp로도 되는지 모르겠다. 일단 가장 먼저 생각난 것은 backtracking이다.

모든 경우를 탐색하며, N이 최대 10이고, 간선의 개수 또한 최대 27이기 때문이다.

 

트리 형태이므로 최대 9개의 간선이 연결되면 되므로 최악의 시간복잡도는 27C9 일 때이다.

주의할 점은, 간선을 연결하지 않을 때, cur은 증가하고 cnt는 증가하지 않는단 점인데,

cnt==N-1일 때에만 리턴하는 것이 아닌, cur이 더이상 간선정보를 접근할 수 없는 index일 때도 리턴을 해주어야 한다.

 

백트래킹으로 간선을 연결해주고, 간선이 N-1개 연결됐다면 트리형태인지 체크.

트리형태라면 값이 최소일 때 갱신해주도록 하자.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 11;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N, M, d[MAX], in[MAX], p[MAX], ret = INF;
vector<pair<int, pi>> v;
vector<pi> ans, tmp;
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	if (a > b)
		swap(a, b);
	p[b] = a;
	return true;
}
bool check() {
	for (int i = 2; i <= N; i++) {
		if (find(i) != find(1))
			return false;
	}
	return true;
}
void solve(int cur, int cnt, int val) {
	if (cnt == N-1) {
		for (int i = 1; i <= N; i++) {
			p[i] = i;
		}
		for (auto i : tmp) {
			merge(i.first, i.second);
		}
		if (check() && ret > val) {
			ret = val;
			ans.clear();
			ans = tmp;
		}
		return;
	}
	if (cur >= v.size())
		return;
	solve(cur + 1, cnt, val);
	int n1 = v[cur].second.first;
	int n2 = v[cur].second.second;
	if (in[n1] < d[n1] && in[n2] < d[n2]) {
		tmp.push_back(v[cur].second);
		in[n1]++; in[n2]++;
		solve(cur + 1, cnt + 1, val + v[cur].first);
		tmp.pop_back();
		in[n1]--; in[n2]--;
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	if (N == 1) {
		cout << "YES\n";
		return 0;
	}
	for (int i = 1; i <= N; i++) {
		cin >> d[i];
		p[i] = i;
	}
	while (M--) {
		int a, b, cost;
		cin >> a >> b >> cost;
		if (a > b)
			swap(a, b);
		v.push_back({ cost, {a,b} });
	}
	solve(0, 0, 0);
	if (ans.empty()) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
		for (auto i : ans) {
			cout << i.first << " " << i.second << "\n";
		}
	}
}

---

당연히 mst 문제일 줄 알았는데, 차수 하나를 추가하여 조건이 추가되니

np-complete가 돼버리는 재밌는 문제였다.

이러한 경험이 쌓이면서 어떠한 알고리즘으로 접근해야 할지 눈이 뜨이는 게 아니겠는가 ㅎㅎ