풀이 방법
DFS함수의 인자로 index를 받고 재귀 호출하는 방식으로 문제를 풀이하였다.
만약 index가 삭제할 노드의 인덱스인 경우 삭제할 노드의 부모 노드의 자식이 1명일 경우(삭제당하는 노드 하나) cnt를 +1 해주었다.
그리고 return을 함으로써 삭제할 노드의 자식은 탐색하지 않았다
index가 삭제할 노드의 인덱스가 아닌데 자식이 empty인 경우에도 cnt를 +1 해주었다.
다음 자식이 여러있고 삭제할 index가 아닌 경우 DFS를 재귀 호출하여 탐색해 주었다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> child;
vector<int> parent;
int remove_, cnt = 0;
void DFS(int index) {
if (index == remove_) {
if (child[parent[index]].size() == 1) cnt++;
return;
}
if (child[index].empty()) {
cnt++;
return;
}
for (int i = 0;i < child[index].size();i++) {
DFS(child[index][i]);
}
return ;
}
int main() {
int N, root;
cin >> N;
child.resize(N);
for (int i = 0;i < N;i++) {
int num;
cin >> num;
parent.push_back(num);
if (num != -1) {
child[num].push_back(i);
}
if (num == -1) root = i;
}
cin >> remove_;
DFS(root);
cout << cnt <<endl;
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준] 감시 피하기 18428번 (python) (0) | 2021.06.11 |
---|---|
[백준] 연산자 끼워넣기 14888번 (python) (0) | 2021.06.10 |
[백준] 탈출 3055번 (c++) (0) | 2021.06.01 |
[백준] 벽 부수고 이동하기 2206번 (c++) (0) | 2021.05.31 |
[백준] 적록색약 10026번 (c++) (0) | 2021.05.27 |