[백준] #1068 트리

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

1068번: 트리

1. 해결방법

BFS를 통하여 해결하였고, 트리를 Vector에 저장하는 방법을 몰라서 찾아보았다

---

2. 코드

트리문제 유형을 공부해보지 못해서 고생했다. 특히 비교하는 부분 코드가 수정할 수 있을거 같으므로 나중에 다시 풀어볼 예정이다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int M;
int D;
int root;
int result = 0;
queue<int> q;
vector<int> t[51];

void BFS() {
    if (root == D) return;
    q.push(root);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < t[node].size(); i++) {
            if (t[node][i] != D) {
                q.push(t[node][i]);
                if (!t[t[node][i]].size() || (t[t[node][i]].size() == 1 &&t[t[node][i]][0] == D)){
                    result++;
                }
            }
            else {
                if (root == node && t[node].size() <=1) result++;
            }
        }
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> M;
        if (M == -1) root = i;
        else t[M].push_back(i);
    }
    cin >> D;
    BFS();
    cout << result;
    return 0;
}