문제 링크 : https://www.acmicpc.net/problem/1068
이 문제는 그저 단말노드를 구하면 되는 문제 입니다.
트리를 전부 돌며 단말노드의 개수를 구하면 되는 문제 입니다.
저는 해당 인덱스의 배열의 원소의 크기가 0인 경우 단말노드로 세었습니다.
하지만, 여기서는 삭제할 노드를 봐야 합니다.
크게 2가지 경우가 있습니다.
1. 지금 검사할 노드가 지울 노드인 경우
2. 지금 검사중인 "배열"의 원소가 지울노드를 포함하는 경우
이 두가지의 경우 return 해주면 되는 문제 입니다.
소스코드 :
이 문제는 그저 단말노드를 구하면 되는 문제 입니다.
트리를 전부 돌며 단말노드의 개수를 구하면 되는 문제 입니다.
저는 해당 인덱스의 배열의 원소의 크기가 0인 경우 단말노드로 세었습니다.
하지만, 여기서는 삭제할 노드를 봐야 합니다.
크게 2가지 경우가 있습니다.
1. 지금 검사할 노드가 지울 노드인 경우
2. 지금 검사중인 "배열"의 원소가 지울노드를 포함하는 경우
이 두가지의 경우 return 해주면 되는 문제 입니다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <vector>
using namespace std;
int cnt = 0;
void Recursive(vector<vector<int > > & v, int root, const int forbid) {
// 경우 1
if (root == forbid)
return;
if (v[root].size() == 0) {
cnt++;
return;
}
bool flag = false;
for (int i = 0; i < v[root].size(); i++) {
if (v[root][i] != forbid) {
flag = true;
Recursive(v, v[root][i], forbid);
}
}
// 경우 2
if (!flag) cnt++;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int root;
vector<vector<int> > v(n);
for (int i = 0; i < n; i++) {
int k;
cin >> k;
if (k != -1)
v[k].push_back(i);
else {
root = i;
}
}
int t;
cin >> t;
Recursive(v, root, t);
cout << cnt;
}
| cs |
댓글
댓글 쓰기