[BOJ] 1068 트리 c++ (트리 그래프, int형 dfs문 활용)

 

https://www.acmicpc.net/problem/1068

 

 

✔ 문제이해

특정 노드를 지웠을 때, 트리의 리프노드(더이상 자식노드가 없는 노드)의 개수를 구하여라.

0~N-1개 까지의 노드들로 구성되어있다.

 

✔ 풀이 + 코드

처음에는 dfs를void 함수로 만들어 vector list에 값이 존재할 경우 재귀문을 타고, 존재하지 않으면 리프노드의 수를 올리는 방식으로 만들었지만, 반례에서 자꾸 막히게 되었다.

또한 rootnode를 무조건 0이라고 생각하면 또 틀리게 된다.

이 반례를 참고하여 틀린 부분을 알았다 : https://www.acmicpc.net/board/view/112681

 

아래 코드는 dfs를 돌 때마다 자식 노드의 수를 확인해주어서 자식노드가 없으면 1을 반환에 ret에 차곡차곡 더해주는 방식의 풀이다. 

 

#include <iostream>
#include <vector>
using namespace std;

int N, nodeNum, delNode, rootNode;
vector<int> trees[54];

int dfs(int here)
{
    int ret = 0;
    int child = 0;

    for(const auto& there : trees[here]){
        if(there == delNode) continue;
        ret += dfs(there);
        child++;
    }
    if(child == 0) return 1;
    return ret;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; ++i)
    {
        cin >> nodeNum;
        if(nodeNum == -1) rootNode = i;
        else trees[nodeNum].push_back(i);
    }

    cin >> delNode;
    if(delNode == rootNode){
        cout << 0 << "\n";
        return 0;
    }

    cout << dfs(rootNode) << endl;
    return 0;
}

 

✔ 피드백

• 푸는 방법은 정말 금방 생각났지만 역시 구현에서 반례들에 자꾸 막혔다. ㅜㅜ
• int형의 재귀문을 활용한 방식이라고 내게 느껴진다. 나도 잘 쓸 수 있도록 연습해야겠다.