[백준/C++] 1068번: 트리

문제

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

1068번: 트리

---

문제 요약

N개 노드로 이루어진 트리에서 각 노드들의 부모 노드의 정보를 입력 받는다.

+ 0번 노드 ~ N - 1번 노드까지 존재한다.

 

해당 트리에서 노드 하나를 지웠을 때, 리프 노드의 개수를 출력한다.+ 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

---

코드

#include <iostream>
#include <vector>

#define MAX_N 50

using namespace std;

int n, remove_node, root;

int cnt;

vector<int> edges[MAX_N + 1];

void dfs(int x) {
    bool isLeaf = true;
    
    // 루트노드가 삭제되었을 경우 
    if (x == remove_node) return;

    for (int i = 0; i < edges[x].size(); i++) {
        int y = edges[x][i];

        // 삭제된 노드라면 탐색 중단
        if (y == remove_node) continue;

        dfs(y);
        isLeaf = false; // 갈 수 있는 노드가 있으므로 리프 노드가 아님.
    }

    if (isLeaf) cnt++;
}

int main() {
    // 입력
    cin >> n;

    for (int i = 0; i < n; i++) {
        int par_node;
        cin >> par_node;

        if (par_node == -1) {
            root = i;
            continue;
        }

        edges[par_node].push_back(i);
    }

    cin >> remove_node;

    // 루트 노드에서 dfs를 진행
    dfs(root);
    
    cout << cnt;

    return 0;
}

---

코드 설명

각 노드들의 부모 노드 정보를 입력 받고, 인접 리스트 형태로 트리 정보를 저장한다.

 

이 때, 부모 노드에서 자식 노드를 향하는 간선의 형태로 저장한다.

 

+ edges[i]: i번 노드에서 갈 수 있는 노드 번호를 갖는 vector

 

루트 노드에서 깊이 우선 탐색 DFS를 진행한다.

 

이 때, bool형 변수 isLeaf를 사용하여 해당 노드에서 갈 수 있는 노드가 존재하는지를 체크한다.

(없으면 리프 노드이고, 있으면 리프 노드가 아니다.)

 

추가적으로, DFS를 진행하면서 삭제된 노드가 있다면 탐색을 종료한다.

 

탐색이 종료되었을 때의 리프 노드 개수를 출력한다.