1068_트리

Concept & Idea

이 문제는 트리의 노드가 중간에 사라지면, 그 트리 하단부를 제외한 나머지 노드의 리프노드 수를 구하는 문제이다. 
처음에 생각을 잘못해서 전체 노드의 리프 노드 수를 구하고, 사라진 노드의 리프노드 수의 차로 결과를 냈는데, 그렇게 하면 문제가 있다. 

만약 특정 노드가 사라졌을 때, 루트노드도 리프 노드가 되는경우! 이다

그 부분만 수정해서 풀까 했는데,, 사실 deleted_node 자체를 탐색하지 않음으로 Dfs 함수 한번으로 해결 할 수 있는 문제였다. 
인접 행렬에서 deleted_node가 들어있으면, 해당 노드는 탐색하지 않고, 나머지 리프 노드들의 수를 누적해서 해결할 수 있다. 
Dfs 를 Void 함수로 작성해서 많이 풀곤 하는데, Int 를 반환하는 함수로 누적합을 더하니 전역변수 하나를 제거할 수 있었다. :) 

Code

#include <iostream>
#include <vector>
using namespace std;
vector<int> vec[51];
int dfs(int cur_node, int deleted_node){
    int child = 0;
    for(int i=0; i<vec[cur_node].size(); i++) {
        if(vec[cur_node][i]!=deleted_node) {
            child += dfs(vec[cur_node][i], deleted_node);
        }
    }
    if(child)
        return child;
    else
        return 1;
}
int main() {
    int n;
    cin>>n;
    int root = 0;
    for(int i=0; i<n; i++) {
        int parent_node;
        cin>> parent_node;
        if(parent_node == -1)
            root=i;
        else
            vec[parent_node].push_back(i);
    }
    int deleted_nodes;
    cin>>deleted_nodes;
    if(root==deleted_nodes)
        cout<<0<<endl;
    else
        cout<<dfs(root, deleted_nodes)<<endl;
}

 

Fealing

처음에도 삭제되는 노드는 아예 탐색하지 않으면 되지 않을까? 라고 생각을 하긴 했지만, 
왜인지 모르게 그냥 루트의 리프노드들과 사라지는 노드의 리프노드들의 갯수 차로 해결할 수 있을 것 같아 그렇게 풀었는데..
생각해보면 바보같은 생각이었다.

ㅠㅠ