트리
알고리즘 구분 : 트리, 그래프 이론
문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
.png)
이제 리프 노드의 개수는 1개이다.
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
예제 입력 1
5
-1 0 0 1 1
2
예제 출력 1
2
예제 입력 2
5
-1 0 0 1 1
1
예제 출력 2
1
예제 입력 3
5
-1 0 0 1 1
0
예제 출력 3
0
예제 입력 4
9
-1 0 0 2 2 4 4 6 6
4
예제 출력 4
2
문제 풀이
처음 문제를 접근할 때에는 문제 제목의 트리와 예제 그림만 보고, 완전 이진 트리 형식으로 간주하여 구현을 하였다가 문제를 틀렸다. 문제 내에 이진 트리라는 것을 의미하는 문장이 하나도 없는데도 불구하고 당연하듯이 문제를 풀고 있었다. 문제를 완벽하게 읽지 않고 속단하는 습관을 고쳐야 할 필요가 있을 것 같다.
완전 이진 트리 형식으루 구현하였던 소스 코드
#include <bits/stdc++.h> using namespace std; int n, del; struct node { int parent = -1; int left = -1; int right= -1; bool remove = false; }; vector<node> tree(51); void connect(int input, int index); void solve(); int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i++) { int input; cin >> input; connect(input, i); } cin >> del; // 2로 입력받으면, 2번째 index니까 1임 solve(); return 0; } void connect(int input, int index) { node temp; if(input == -1) { temp.parent = input; } else if(input > -1) { temp.parent = input; if(tree[input].left == -1) { tree[input].left = index; } else if(tree[input].left != -1) { tree[input].right = index; } } tree[index] = temp; } void solve() { int cnt, now; queue<int> q; vector<int> v; q.push(del); while(!q.empty()) { now = q.front(); tree[now].remove = true; q.pop(); if(tree[now].right != -1) { q.push(tree[now].right); } if(tree[now].left != -1) { q.push(tree[now].left); } } cnt = 0; for(int i = 0; i < n; i++) { if(tree[i].remove == false && tree[i].right == -1 && tree[i].left == -1) { cnt++; } } cout << cnt << endl; }
구조체를 이용해 부모 노드와 자식 노드를 무엇으로 가지는지 일일이 정보로 가질 수 있도록 구현하여 그래프 탐색을 진행하여 제거 및 리프 노드 개수를 확인할 수 있도록 구현하면 되는 문제이다.
문제를 풀면서 제일 조심해야 되는 케이스가 있다.
입력
4
-1 0 1 2
2
출력
1
위의 예제이다. 위는 아래 자식 노드들이 지워질 예정이므로 두 번째 노드가 리프 노드가 된다. 하지만, 내 구현 방식에서는 자식 노드들이 지워지는 것을 변수를 통해 확인하는 방법일 뿐 실제로 자식 노드 vector에서 지우지 않았기에, 위의 케이스를 확인하는 부분을 따로 구현할 필요가 있었다. 문제를 풀 때, 조심해야할 엣지 케이스인 것 같다.
또한 문제를 풀 때, 재귀를 이용한 dfs로 구현하였으나, 종료 조건을 제대로 설정하지 못하여, bfs방식으로 처리했다. dfs가 개인적으로는 bfs보다 구현에서 약간의 까다로움이 더 있는 것 같다. 연습을 조금 더 해야할 필요가 있을 것 같다.
소스코드
#include <bits/stdc++.h>
using namespace std;
int n, del, cnt;
struct node {
int parent;
bool remove;
vector<int> child;
};
vector<node> tree(51);
void bfs(int start);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> tree[i].parent;
tree[i].remove = false;
if(tree[i].parent != -1) {
tree[tree[i].parent].child.push_back(i);
}
}
cin >> del;
bfs(del);
cnt = 0;
for(int i = 0; i < n; i++) {
if(tree[i].remove == false) {
if(tree[i].child.size() == 0) {
cnt++;
}
else if(tree[i].child.size() > 0) {
bool check = true;
for(int j = 0; j < tree[i].child.size(); j++) {
if(tree[tree[i].child[j]].remove == false) {
check = false;
}
}
if(check) {
cnt++;
}
}
}
}
cout << cnt << endl;
return 0;
}
void bfs(int start) {
int now;
queue<int> q;
q.push(start);
tree[start].remove = true;
while(!q.empty()) {
now = q.front();
q.pop();
for(int i = 0; i < tree[now].child.size(); i++) {
if(tree[tree[now].child[i]].remove == false) {
tree[tree[now].child[i]].remove = true;
q.push(tree[now].child[i]);
}
}
}
}- 문제 출처 : https://www.acmicpc.net/problem/1068
- 해당 풀이는 백준에서 "맞았습니다!!"판정을 받았습니다.
