[BOJ] 백준 23237. How Many Subtrees? (Gold IV)

하위 서브트리의 개수를 모조리 파악하는 문제이다.

사실 흔히 보았던 문제들이랑 거의 비슷할 줄 알았고,

범위도 작아서 쉽게 해결할 수 있을 줄 알았는데,

서브트리의 크기에 상관없이 모든 서브트리는 모조리 다 출력해야 되는 문제였어서 WA를 좀 받았었다.

 

문제는 아래와 같다.

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

23237번: How Many Subtrees?

---

의식의 흐름 및 해설

처음에 treedp로 풀려다가, N 범위가 매우 작아 9!이든 NlgN*9!이든 상관없을 것 같아 백트래킹으로 시도해보았다.

테스트케이스 개수가 명시가 돼있지 않아 시간복잡도 상으로 조금 불안했지만, 일단 연산 횟수가 1억번 미만이기 때문에 백트래킹으로 해보았다.

 

백트래킹으로 간선을 포함할지 안포함할지 결정하면 된다.

처음에 나는 간선을 연결할 때, 연결할 간선에 포함된 각 노드의 차수가 0이 아닌 노드가 존재하면 같은 컴포넌트로 연결할 수 있을 듯하여 차수를 비교하면서 넣을지 안넣을지 여부를 결정하였다.

근데 그렇게 조건을 따지면서 백트래킹을 하면 순서에 따라 영향을 미칠 수 있으므로 WA를 받는다.

따라서 백트래킹으로 풀려면 일단 포함/미포함으로 갈래를 나눈 후, 완성된 버전에서 오직 하나의 컴포넌트인지 유니온파인드로 체크해주어야 한다. 백트래킹 내에서 조건을 따지면 안된다.

 

그런데 사실 treedp로도 풀 수 있다.

백트래킹으로 AC를 받은 후 treedp로도 해결해보았는데,

일단 자기 자신으로만 이루어진 경우도 하나의 서브트리이므로 기본적으로 dp[cur]=1이다.

그리고 자신의 자식노드들의 서브트리의 모양에 따라 자신의 서브트리 모양이 달라지므로 dp[cur]+=dp[i]*dp[j]* ... 꼴로 곱해짐을 알 수 있다.

자신의 서브트리를 구할 때 자식노드의 서브트리에 자신이 반드시 포함돼야 하며, 자기 자신으로만 서브트리도 가능하므로 점화식 꼴은 dp[cur]+=(dp[i]+1)*(dp[j]+1)* ... (자신의 자식노드들: i, j, ...) 이다.

---

코드 (backtracking + union_find)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#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<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 12;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const ll MOD = 1e9 + 7;
vector<pi> v, c;
int t, N, ans, d[MAX], p[MAX];
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 = 0; i < N; i++) {
		p[i] = i;
		d[i] = 0;
	}
	for (int i = 0; i < c.size(); i++) {
		merge(c[i].first, c[i].second);
		d[c[i].first]++;
		d[c[i].second]++;
	}
	int k = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (!d[i])
			continue;
		if (!cnt) {
			cnt++;
			k = find(i);
			continue;
		}
		if (k != find(i))
			return false;
	}
	return true;
}
void solve(int cur, int cnt) {
	if (cur == N - 1) {
		if (check())
			ans++;
		return;
	}
	c.push_back(v[cur]);
	solve(cur + 1, cnt + 1);
	c.pop_back();
	solve(cur + 1, cnt);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	while (cin >> N && N) {
		ans = N;
		fill(d, d + MAX, 0);
		v.clear();
		c.clear();
		for (int i = 0; i < N - 1; i++) {
			int a, b;
			cin >> a >> b;
			if (a > b)
				swap(a, b);
			v.push_back({ a,b });
		}
		solve(0, 0);
		cout << "Case " << ++t << ": " << ans - 1 << "\n";
	}
}

---

코드 (treedp)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#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<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 12;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const ll MOD = 1e9 + 7;
vector<int> v[MAX], c[MAX];
int t, N, ans, d[MAX];
bool visit[MAX];
void init(int cur) {
	visit[cur] = true;
	for (auto i : v[cur]) {
		if (!visit[i]) {
			c[cur].push_back(i);
			init(i);
		}
	}
}
int dp(int cur, int prev) {
	int& ret = d[cur];
	if (ret != -1)
		return ret;
	ret = 1;
	for (auto i : c[cur]) {
		ret *= (1 + dp(i, cur));
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	while (cin >> N && N) {
		ans = 0;
		fill(d, d + MAX, 0);
		fill(visit, visit + MAX, false);
		for (int i = 0; i < N; i++) {
			v[i].clear();
			c[i].clear();
		}
		for (int i = 0; i < N - 1; i++) {
			int a, b;
			cin >> a >> b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		init(0);
		memset(d, -1, sizeof(d));
		for (int i = 0; i < N; i++)
			ans += dp(i, -1);
		cout << "Case " << ++t << ": " << ans << "\n";
	}
}

---

정답비율 100%에서 84%로 떡락시킨 장본인 ㅠㅠㅠ

꽤나 재밌는 문제였다.

treedp 감도 익힐 수 있었고, 그 외에 N 범위가 작아 백트래킹+분리집합으로도 풀리는 재밌었던 문제.

icpc 문제이기도 하고, 학교 내에서 푼 사람이 없는 랭작하기 좋은 문제여서 풀고나서 더 기분 좋았던 문제이다.