백준 6603 로또 (bfs)

이 문제는 죽일 노드를 받고 리프 노도의 갯수를 구하면된다

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

풀이법

이문제에서 죽이는 노드 == 탐색하지 않는 노드
이렇게 하면 그 노드를 죽이게 되어서 그 밑으로 내려가지 않게 된다.!

여기서 예외처리에서 루트노드를 죽일 수도있다는 것이다
루튼노트가 죽지 않았으면 루트부터 탐색을 수행하면된다.

#include <bits/stdc++.h>


using namespace std;

int n, Kill, rootNode, res;
vector<int> v[51];
vector<int> ans;
bool visited[51];

void bfs(int idx) {

    queue<int> q;
    q.push(idx);
    visited[idx] = 1;


    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        int chidCnt = 0;
        for (int i = 0; i < v[x].size(); i++)
        {
            int nx = v[x][i];
            if (!visited[nx]) {
                visited[nx] = 1;
                q.push(nx);
                chidCnt++;
            }
        }
        if (chidCnt == 0) {
            res++;
        }
    }

}
int main() {

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int tmp = 0; cin >> tmp;
        if (tmp == -1) {
            rootNode = i;
        }
        else
        {
            v[tmp].push_back(i);
            v[i].push_back(tmp);
        }

    }
    cin >> Kill;
    visited[Kill] = 1;

    if (!visited[rootNode]) bfs(rootNode);
    cout << res;
    return 0;
}