[C++] 백준/Gold/1068. 트리

문제: 트리 (백준 1068번)

문제 분석

루트 없는 트리가 주어질 때, 특정 노드를 삭제하면 남은 트리에서 리프 노드 개수를 구하는 문제이다.

1. 입력 처리
   • graph[i]: 각 노드의 자식들을 저장하는 인접 리스트.
   • depth[i]: 각 노드가 몇 개의 자식을 가지는지 저장.
2. 삭제할 노드(target) 반영
   • 부모 노드에서 삭제할 노드의 연결을 끊음 (자식 수 감소).
   • BFS를 활용하여 삭제할 노드 및 해당 서브트리를 모두 제거 (depth 값을 -1로 설정).
3. 리프 노드 개수 계산
   • depth[i] == 0인 노드 개수를 세어 출력.

---

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; cin >> n;
    vector<int> depth(n);
    vector<vector<int>> graph(n);

    // 트리 입력 처리
    for (int i = 0; i < n; i++) {
        int parent; cin >> parent;
        if (parent == -1) continue;  // 루트 노드는 제외
        depth[parent]++;  
        graph[parent].push_back(i);
    }

    // 삭제할 노드 입력
    int target; cin >> target;

    // 부모 노드에서 target 제거
    for (int i = 0; i < n; i++) {
        for (const int& node : graph[i]) {
            if (node == target) {
                depth[i]--;  
                break;
            }
        }
    }

    // BFS로 target 서브트리 삭제
    queue<int> bfs;
    bfs.push(target);
    while (!bfs.empty()) {
        int node = bfs.front();
        bfs.pop();
        depth[node] = -1;  // 삭제된 노드 표시
        for (const int& next : graph[node]) {
            bfs.push(next);
        }
    }

    // 리프 노드 개수 출력
    cout << count(depth.begin(), depth.end(), 0);
}