1068

• tree

조건을 명확히 파악하기 힘든 문제입니다.

아직 이 문제를 푸시지 않은 분이라면
아래에 정리를 남길테니 읽어 보시고
다시 풀어보시는 것도 좋은 방법일 것 같습니다.

1. 주어지는 노드의 수는 최소 1개 최대 50개이다.

2. 해당 트리는 이진 트리가 아닐 수 있다.

3. 두번째 줄 입력으로 주어지는 숫자는 각각 2가지 정보를 가지고 있다.

   • 입력 숫자 그 자체는 자신의 부모 숫자이다.
   • 입력 숫자의 순서 그 자체는 자신의 숫자이다.
     (ex. 0번째로 들어온 숫자가 4라면, 4의 자식은 0이다.)

4. 루트는 부모가 없기 때문에 -1 이라는 숫자를 가르킨다.
   하지만 루트의 입력 순서는 반드시 존재하기 때문에
   루트의 숫자 정보를 순서로 유추할 수 있다.

5. 이것은 rooted tree이기 때문에 루트는 항상 존재하며
   루트가 2개 이상 주어지는 경우는 없다.

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[50];
int a[50];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, t, f, 
        rt = 1, rv,
        cnt = 0; 
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> t;
        a[i] = t;
        if (t < 0) rv = i;
        else v[t].push_back(i);
    }

    cin >> f;
    if (a[f] < 0) rt--;

    for (int i = 0; rt && i < v[a[f]].size(); i++)
        if (v[a[f]][i] == f) {
            v[a[f]].erase(v[a[f]].begin() + i);
            break;
        }

    queue<int> q;
    q.push(rv);

    while (rt && !q.empty()) {
        int p = q.front();
        if (!v[p].size())
            cnt++;
        else {
           for (int i = 0; i < v[p].size(); i++)
                q.push(v[p][i]);
        }
        q.pop();
    }

    cout << cnt;
    
    return 0;
}