취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23237번 문제인 How Many Subtrees?이다.
문제는 아래 링크를 확인하자.

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

트리가 입력으로 주어질 때, 찾을 수 있는 subtree의 개수를 구하는 문제이다.

노드의 개수 N이 10개 이하이므로, 2^N - 1가지(노드집합이 빈 경우 제외: 그림의 예시로 확인 가능)의 노드구성 각각에 대하여 그런 노드구성의 트리가 가능한지 하나하나 확인해도 좋지만 DP를 이용하여 문제를 해결해보자.

트리의 루트를 임의로 하나 정하자. 이 트리의 모든 서브트리는 이 루트를 포함하거나 루트를 포함하지 않는다는 것은 자명하다.

루트를 포함하지 않는 모든 서브트리는 루트와 이어진 각 노드를 루트로 하는 서브트리에 포함된 모든 트리의 수의 합과 같다.

루트를 포함하는 서브트리의 개수는 루트와 이어진 각 노드에 대하여 (그 노드를 루트로 하는 서브트리에서 루트를 포함하는 서브트리의 개수 + 1) 들을 1에 곱한 것과 같다. 루트를 포함하는 서브트리의 수를 세는 것이므로 루트는 당연히 선택을 하였을 것이고, 루트와 연결된 각 노드에 대하여 어떤 서브트리를 고를지, 또는 그 노드와 연결을 하지 않을 것인지(+1)의 경우의 수들을 곱하면 되기 때문이다.

위의 내용을 구현하여 문제를 해결해보자.

아래는 제출한 소스코드이다.

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

vector<int> G[10];

pair<int,int> dfs(int current, int parent) { // {전체, 루트포함}
	int total = 0, rooted = 1;
	for (auto node : G[current]) {
		if (node == parent) continue;
		auto temp = dfs(node, current);
		total += temp.first, rooted *= temp.second + 1;
	}
	total += rooted;
	return make_pair(total, rooted);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	int N; cin >> N;
	while (N) {
		for (auto& g : G) g.clear();
		for (int i = 1; i < N; i++) {
			int x, y; cin >> x >> y;
			G[x].emplace_back(y);
			G[y].emplace_back(x);
		}

		cout << "Case " << T++ << ": " << dfs(0, 0).first << '\n';
		cin >> N;
	}
}