[Problem Solving] BOJ 1068 : 트리

문제 링크 : https://www.acmicpc.net/problem/1068

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, root, del, cnt = 0;
vector<int> graph[51];
int visited[51];

void input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int j;
        cin >> j;
        if (j == -1)
            root = i;
        else
        {
            graph[j].push_back(i);
            graph[i].push_back(j);
        }
    }
    cin >> del;
    if (root == del)
    {
        cout << 0 << endl;
        exit(0);
    }
}

void cntLeaves(int r)
{
    visited[r] = 1;
    bool flag = false;
    for (auto child : graph[r])
    {
        if (child == del)
            continue;
        if (!visited[child])
        {
            flag = true;
            cntLeaves(child);
        }
    }
    if (!flag)
        ++cnt;
}

void solve()
{
    fill(&visited[0], &visited[N + 1], 0);
    cntLeaves(root);
}

void output()
{
    cout << cnt << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solve();
    output();

    return 0;
}

트리가 주어졌을 때 특정 노드를 삭제 했을 경우의 리프 노드의 수를 구하는 문제이다. 리프 노드의 특징은 자식 노드가 없다는 특징을 이용해서 DFS로 풀 수 있다.

 

1. 입력을 받는데, 루트 노드를 지우고자 한다면 리프 노드는 없기 때문에 0을 출력하기 프로그램을 종료한다.

2. 방문 테이블을 0으로 초기화한다.

3. 루트 노드를 기점으로 DFS를 실행한다.

4. 해당 노드의 방문 테이블 요소를 1로 바꾸고, 자식 노드가 삭제하고싶은 노드라면 continue, 그렇지 않고 아직 방문하지 않은 노드라면 적어도 하나의 자식 노드가 있다는 flag를 true로 바꾼 후, DFS를 재귀 호출한다. 자식 노드가 존재 하지 않아 flag가 false 라면 cnt를 증가시킨다.

5. DFS 탐색이 끝난 후의 cnt값이 정답이 된다.