[백준] 트리 1068번 (c++)

출처 : 1068번: 트리 (acmicpc.net)

1068번: 트리

풀이 방법

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;
}