[백준 c++] 1068 트리

문제 설명

https://www.acmicpc.net/problem/1068
첫째 줄에 트리의 노드의 개수 N(0<N<=50)이 주어진다.
둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다.
만약 부모가 없다면 (루트) -1이 주어진다.
셋째 줄에 입력으로 주어지는 노드를 지웠을 때, 리프 노드의 개수를 출력하는 문제다.

아이디어

문제를 잘못 이해해서 헤맸던 아주 열받았던 문제다^^..
두 번째 입력이 -1 0 0 1 1 이라면

0번 째 노드:루트 node
1번 째 노드의 부모: 0
2번 째 노드의 부모: 0
3번 째 노드의 부모: 1
4번 째 노드의 부모: 1
이렇게 되는 것이다.

1. map[부모노드][자식노드] 형태로 입력받기
2. 삭제할 노드(m)를 기준으로 dfs를 이용하여 자식 노드들까지 -2로 바꿈
3. bfs로 root노드부터 시작하여 leaf노드 개수 구하기

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, a, root, flag;
int map[51][51];
int del[51];
int visited[51];
int visited2[51];
int leaf;
queue<int> q;

void bfs(int x)
{
    q.push(x);
    while (!q.empty())
    {
        int node = q.front();
        int cnt = 0;
        q.pop();
        for (int i = 0; i < n; i++)
        {
            if (map[node][i] == 1 && visited[i] == 0)
            {
                cnt++; //자식이 하나라도 잇으면
                visited[node] = 1;
                q.push(i);
                if (node == m || del[node] == -2) //부모의 값이 삭제될 노드이면
                {
                    del[node] = -2;
                    del[i] = -2;
                }
                else if (i == m)
                {
                    del[i] = -2;
                    cnt--;
                }
            }
            else if (node == m) //자식 없어도 삭제될 노드면
                del[node] = -2;
        }
        //자식이 없는 leaf노드
        if (cnt == 0 && del[node] != -2 && visited2[node] == 0)
        {
            leaf++;
            visited2[node] = 1;
        }
    }
}

void dfs(int y)
{
    for (int i = 0; i < n; i++)
    {
        if (map[y][i] == 1)
        {
            map[y][i] = -2;
            dfs(i);
        }
    }
    return;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        if (a == -1)
            root = i;
        else
        {
            map[a][i] = 1;
        }
    }

    cin >> m; //삭제할 노드

    for (int i = 0; i < n; i++)
    {
        if (i == m)
        {
            dfs(m);
            flag = 1;
            break;
        }
    }

    if (flag) //자식이 없는 노드라면
    {
        for (int i = 0; i < n; i++)
        {
            if (map[i][m] == 1)
            {
                map[i][m] = -2;
                break;
            }
        }
    }

    bfs(root);

    cout << leaf << "\n";
}