이번에는 백준 1068번 트리 문제를 풀어보았습니다.
이 문제는 트리에서 특정 노드를 하나 지웠을 때, 남아 있는 트리의 리프 노드 개수를 구하는 문제입니다.
처음에는 실제로 target 노드를 트리 구조에서 지우는 방식으로 접근했고, 이후에는 DFS 안에서 target을 건너뛰는 방식으로 더 간단하게 정리할 수 있었습니다.
문제 설명
트리에서 리프 노드는 자식이 없는 노드를 의미합니다.
입력으로 각 노드의 부모 정보가 주어지고,
이후 특정 노드 하나를 삭제합니다.
이때 삭제되는 것은 그 노드 하나만이 아니라,
- 그 노드
- 그 노드의 모든 자손
까지 전부 함께 제거됩니다.
최종적으로 남아 있는 트리에서 리프 노드가 몇 개인지를 출력하면 됩니다.
풀이 아이디어
이 문제는 부모 정보가 주어지기 때문에,
먼저 이를 이용해 부모 → 자식 형태의 트리 구조를 만들어야 합니다.
그 뒤 특정 노드를 지운 상태에서 DFS를 돌며 리프 노드 개수를 세면 됩니다.
노드를 지우는 방식은 두 가지로 생각해볼 수 있었습니다.
- V1 : target 노드를 실제로 tree에서 제거하고, target을 가리키는 부모의 연결도 직접 삭제
- V2 : DFS를 돌 때 target이면 아예 들어가지 않도록 처리
두 방식 모두 결국은 삭제된 노드와 그 자손들을 탐색에서 제외한다는 점은 같습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int target;
int N;
vector<vector<int>> tree;
int cnt = 0;
void dfs(int num) {
if (tree[num].size() == 0) {
cnt++;
return;
}
for (int i : tree[num]) {
dfs(i);
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
tree.push_back(vector<int>());
int num;
cin >> num;
if (num == -1) continue;
tree[num].push_back(i);
}
cin >> target;
if (target == 0) {
cout << 0;
return 0;
}
tree[target].clear();
int num = 0;
int flag = true;
while(flag) {
if (num == tree.size())
break;
for (int i=0; i<tree[num].size(); i++) {
if (tree[num][i] == target) {
flag = false;
tree[num].erase(tree[num].begin() + i);
break;
}
}
num++;
}
dfs(0);
cout << cnt;
return 0;
}V1 풀이 흐름
- 부모 정보를 입력받아
tree[parent].push_back(child)형태로 트리를 만든다. - 삭제할 노드
target을 입력받는다. - 만약
target == 0이면 루트가 삭제되는 것이므로 결과는 0이다. tree[target].clear()로 target의 자식들을 지운다.- 이후 전체 트리를 순회하며, target을 자식으로 가지고 있는 부모 노드에서 target을 제거한다.
- 수정된 트리 기준으로 DFS를 돌며 리프 노드 개수를 센다.
- 결과를 출력한다.
V1 구현 포인트
1. 부모 정보로 자식 리스트 만들기
입력은 각 노드의 부모가 주어지므로,
트리를 사용하기 쉽게 만들기 위해 부모 기준 자식 리스트로 바꾸었습니다.
if (num == -1) continue;
tree[num].push_back(i);즉, num이 부모이고 i가 자식이 됩니다.
이렇게 하면 이후 DFS를 하면서 자식들을 따라 내려가기 쉬워집니다.
2. target의 자식들을 먼저 삭제
노드를 삭제하면 그 자손도 함께 제거되므로,
먼저 target 아래에 연결된 자식들을 없애는 방식으로 처리했습니다.
tree[target].clear();이렇게 하면 target 아래로 더 이상 내려가지 않게 됩니다.
3. 부모가 target을 가리키는 연결도 제거해야 함
하지만 tree[target].clear()만으로는 충분하지 않았습니다.
왜냐하면 여전히 부모 노드의 자식 목록 안에는 target이 남아 있기 때문입니다.
그래서 전체 트리를 순회하면서,
누군가가 자식으로 target을 가지고 있으면 그 연결도 직접 지웠습니다.
if (tree[num][i] == target) {
flag = false;
tree[num].erase(tree[num].begin() + i);
break;
}즉, target 노드 자체도 트리에서 완전히 끊어줘야 했던 것입니다.
4. DFS에서 자식이 없으면 리프 노드
이후 DFS에서는 현재 노드의 자식 수가 0이면 리프 노드로 보았습니다.
if (tree[num].size() == 0) {
cnt++;
return;
}즉, 수정된 트리 기준에서 자식이 없는 노드를 세는 방식입니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int target;
int N;
vector<vector<int>> tree;
int dfs(int num) {
int ret = 0;
int child = 0;
for (int i : tree[num]) {
if (i == target) continue;
ret += dfs(i);
child++;
}
if (child == 0)
return 1;
return ret;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
tree.push_back(vector<int>());
int num;
cin >> num;
if (num == -1) continue;
tree[num].push_back(i);
}
cin >> target;
if (target == 0) {
cout << 0;
return 0;
}
cout << dfs(0);
return 0;
}V2 풀이 흐름
- 부모 정보를 이용해 트리를 만든다.
- 삭제할 노드
target을 입력받는다. - 루트가 삭제되는 경우는 바로 0을 출력한다.
dfs(0)으로 루트부터 탐색한다.- DFS에서는 자식을 순회할 때
target이면 아예 건너뛴다. - 실제로 탐색한 자식 수를
child로 센다. - 탐색 가능한 자식이 하나도 없으면 현재 노드를 리프 노드로 보고 1을 반환한다.
- 각 자식에서 반환된 리프 개수를 누적해 최종 결과를 출력한다.
V2 구현 포인트
1. target이면 아예 DFS에 들어가지 않기
두 번째 방식에서는 트리 자체를 직접 수정하지 않았습니다.
대신 DFS를 돌 때 target 노드를 만나면 아예 탐색하지 않도록 했습니다.
if (i == target) continue;이렇게 하면 target과 그 아래 자손들은 자연스럽게 DFS 결과에서 제외됩니다.
즉, 삭제를 구조 수정으로 처리하지 않고, 탐색에서 제외하는 방식입니다.
2. 단순히 size() == 0으로는 부족함
이 방식에서는 중요한 점이 하나 있었습니다.
예를 들어 어떤 노드가 원래는 자식을 가지고 있었더라도,
그 자식이 전부 target이라서 DFS에서 건너뛰게 되면
그 노드는 삭제 이후에는 리프 노드가 됩니다.
그래서 단순히
tree[num].size() == 0으로 판단하면 안 되고,
실제로 DFS에 들어간 자식 수를 따로 세어야 했습니다.
3. 실제 탐색한 자식 수를 child로 세기
그래서 child 변수를 따로 두고,
target이 아닌 자식에 대해서만 증가시키도록 했습니다.
int child = 0;
for (int i : tree[num]) {
if (i == target) continue;
ret += dfs(i);
child++;
}즉, 현재 노드가 가지고 있는 원래 자식 수가 아니라,
삭제 이후에도 남아 있는 자식 수를 세는 방식입니다.
4. 탐색 가능한 자식이 없으면 리프 노드
그 결과 child == 0이면 현재 노드는 리프 노드가 됩니다.
if (child == 0)
return 1;이 부분이 V2의 핵심이었습니다.
즉, 삭제 이후 구조를 기준으로 리프 노드를 판단할 수 있게 됩니다.
