[BOJ 26935 // C++] Släktträffen

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

 

이번에 볼 문제는 백준 26935번 문제인 Släktträffen이다.
문제는 아래 링크를 확인하자.

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

26935번: Släktträffen

이 문제는 주어지는 M개의 노드의 LCA(Lowest Common Ancestor)를 구하는 문제이다.

 

DFS를 이용한 트리DP를 이용해 각 노드를 루트로 하는 서브트리에 포함된 "M개의 노드에 포함되는 노드"의 개수를 구하고, 그 값이 M인 노드 중 가장 깊은 노드를 출력해 문제를 해결할 수 있다.

 

위와 같이 해결하지 않더라도 각 노드에서 DFS를 시도해 해당 노드를 루트로 하는 서브트리의 노드의 개수와 포함하는 "M개의 노드에 포함되는 노드"의 개수를 각각 구한 뒤, 포함하는 "M개의 노드에 포함되는 노드"가 M과 같은 서브트리 중 노드의 개수가 가장 적은 서브트리의 루트를 출력하는 것으로 문제를 해결할 수 있다.

 

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

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

int N, M;
vector<int> G[21];
int num[21];
bool chk = 1;

int dfs(int cur) {
	int ret = num[cur];
	for (auto& nxt : G[cur]) {
		ret += dfs(nxt);
	}

	if (ret == M && chk) cout << cur, chk = 0;

	return ret;
}

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

	cin >> N >> M;
	for (int cur = 1; cur <= N; cur++) {
		int par; cin >> par;
		G[par].emplace_back(cur);
	}

	for (int m = 0; m < M; m++) {
		int x; cin >> x;
		num[x]++;
	}

	dfs(0);
}