트리 관련 문제들입니다. 트리 구현부터 트리에서의 다이나믹 프로그래밍 관련 문제들의 풀이입니다.
BOJ15681 트리와 쿼리
간선 정보가 주어지면 인접 행렬을 사용해서 저장해줍니다. 주어진 루트 번호를 시작으로 DFS를 하며 부모-자식 관계를 만들어줍니다. 이 때, 각 노드 index에 해당하는 배열(numChild)에 자식 노드들의 수를 저장해줍니다.
이러면 쿼리는 O(1)에 처리할 수 있습니다. numChild 배열에는 자식 노드의 개수만 저장되어 있으므로 출력을 할 때는 1을 더해주어야 합니다.
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int N, R, Q;
int V, E, pt;
bool visit[100111];
int numChild[100111];
vector<int> Tree[100111];
void makeTree(int node) {
visit[node] = true;
for(int i = 0; i < Tree[node].size(); i++) {
int child = Tree[node][i];
if(visit[child]) {
continue;
}
numChild[node]++;
makeTree(child);
numChild[node] += numChild[child];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> R >> Q;
memset(visit, false, sizeof(visit));
memset(numChild, 0, sizeof(numChild));
for(int i = 0; i < N - 1; i++) {
cin >> V >> E;
Tree[V].push_back(E);
Tree[E].push_back(V);
}
makeTree(R);
for(int i = 0; i < Q; i++) {
cin >> pt;
cout << numChild[pt] + 1 << "\n";
}
}
BOJ2533 사회망 서비스 (SNS)
트리의 각 노드가 얼리어답터일 때와 아닐 때를 분리하여 트리의 루트부터 DFS 하면서 DP 배열을 채우면 됩니다.
dp[node][1] 은 해당 node가 얼리어답터일 때, node 밑으로의 서브트리의 최소 얼리어답터 수입니다. Node의 child는 얼리어답터가 아닐테니 dp[child][0]을 그대로 더해줍니다. dp[node][2] 은 해당 node가 얼리어답터가 아닐 때, node 밑으로의 서브트리의 최소 얼리어답터 수입니다. Node의 child가 얼리어답터일 수도 아닐 수도 있으니 최솟값을 더해줍니다.
dp[node][1] += dp[child][0]; dp[node][0] += min(dp[child][0], dp[child][1]);
위 점화식으로 DFS를 돌면 됩니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, u, v;
vector<int> Tree[1000111];
int dp[1000111][2];
bool visit[1000111];
void solve(int node) {
visit[node] = true;
dp[node][0] = 1;
for(int i = 0; i < Tree[node].size(); i++) {
int child = Tree[node][i];
if(!visit[child]) {
solve(child);
dp[node][1] += dp[child][0];
dp[node][0] += min(dp[child][0], dp[child][1]);
}
}
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
cin >> u >> v;
Tree[u].push_back(v);
Tree[v].push_back(u);
}
solve(1);
cout << min(dp[1][0], dp[1][1]);
}
BOJ1949 우수마을
사회망서비스 문제와 비슷하게 DP를 풀어주면 됩니다. 이 문제에선 최댓값으로 DP를 돌아줍니다.
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
int N, V, E;
bool visit[100111];
int numPerson[100111];
int dp[100111][2];
vector<int> Tree[100111];
void dfs(int node) {
visit[node] = true;
dp[node][0] = 0;
dp[node][1] = numPerson[node];
for(int i = 0; i < Tree[node].size(); i++) {
int child = Tree[node][i];
if(visit[child]) {
continue;
}
dfs(child);
dp[node][0] += max(dp[child][0], dp[child][1]);
dp[node][1] += dp[child][0];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
memset(visit, false, sizeof(visit));
for(int i = 1; i <= N; i++) {
cin >> numPerson[i];
}
for(int i = 0; i < N - 1; i++) {
cin >> V >> E;
Tree[V].push_back(E);
Tree[E].push_back(V);
}
dfs(1);
cout << max(dp[1][0], dp[1][1]);
}
BOJ2263 트리의 순회
트리 순회 방식 중 inorder와 postorder로 순회했을 때 노드 순서가 주어지면 해당 순서로 preorder 순서를 추정하는 문제입니다.
(1) postorder로 돌았을 때 마지막은 항상 Root 라는 점, (2) inorder에서 root를 기준으로 왼쪽은 서브트리의 왼쪽 노드들, 오른쪽은 서브트리의 오른쪽 노드들 이라는 점, (3) 해당 노드들이 postorder 순서에서 차례대로 나타난다는 점 을 이용해서 재귀함수를 돌려 트리의 Leaf까지 찾아내는 문제입니다. Leaf에 다달으면 해당 인덱스의 inorder 배열을 출력하면서 재귀함수를 빠져나오면 됩니다.
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> inorder;
vector<int> postorder;
vector<int> idx;
void solve(int iS, int iE, int pS, int pE) {
if(iS > iE || pS > pS) {
return;
}
int root = idx[postorder[pE]];
int leftSize = root - iS;
int rightSize = iE - root;
cout << inorder[root] << " ";
solve(iS, root - 1, pS, pS + leftSize - 1);
solve(root + 1, iE, pS + leftSize, pE - 1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
inorder.resize(N + 1);
postorder.resize(N + 1);
idx.resize(N + 1);
for(int i = 1; i <= N; i++) {
cin >> inorder[i];
idx[inorder[i]] = i;
}
for(int i = 1; i <= N; i++) {
cin >> postorder[i];
}
solve(1, N, 1, N);
}