[Baekjoon(백준)][1068번] 트리(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "트리" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 트리에서 특정 노드를 삭제했을 때 남는 트리의 리프 노드(자식이 없는 노드)의 개수를 구하는 문제입니다.문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

1068번: 트리

문제 개요

"트리" 문제는 주어진 트리에서 특정 노드를 삭제했을 때 남는 트리의 리프 노드(자식이 없는 노드)의 개수를 구하는 문제입니다.

문제 해결 아이디어

이 문제를 해결하기 위해 우리는 깊이 우선 탐색(DFS)를 사용합니다. DFS를 통해 각 노드를 방문하면서 해당 노드가 리프 노드인지 확인하고, 삭제된 노드의 자손 노드는 탐색 과정에서 제외합니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int n, r, root; // n: 노드의 개수, r: 삭제할 노드 번호, root: 루트 노드 번호
vector<int> trees[54]; // 각 노드의 자식 노드를 저장하는 벡터 배열

// 깊이 우선 탐색 함수
int dfs(int here) {
    int ret = 0; // 리프 노드의 개수
    int child = 0; // 자식 노드의 개수
    for (int there : trees[here]) {
        if (there == r) continue; // 삭제할 노드의 자손 노드는 탐색하지 않음
        ret += dfs(there);
        child++;
    }
    if (child == 0) return 1; // 자식 노드가 없으면 리프 노드
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    int temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        if (temp == -1) root = i; // 루트 노드 설정
        else trees[temp].push_back(i); // 자식 노드 추가
    }
    cin >> r; // 삭제할 노드 번호 입력
    if (r == root) { // 삭제할 노드가 루트 노드인 경우
        cout << 0 << "\n";
        return 0;
    }
    cout << dfs(root) << "\n"; // 리프 노드의 개수 출력
    return 0;
}

코드 설명

위 코드는 루트 노드부터 시작하여 깊이 우선 탐색을 통해 트리를 순회합니다. 각 노드를 방문할 때마다 자식 노드가 있는지 확인하고, 자식 노드가 없다면 해당 노드는 리프 노드입니다. 삭제할 노드와 그 자손 노드는 탐색에서 제외합니다. 마지막으로, 탐색을 통해 구한 리프 노드의 총 개수를 출력합니다.

결론

이 문제의 핵심은 깊이 우선 탐색을 사용하여 리프 노드의 개수를 구하는 것입니다. 특정 노드를 삭제한 후에 남은 트리에서 리프 노드의 개수를 정확히 구하기 위해서는 삭제할 노드와 그 자손 노드를 탐색 과정에서 제외해야 합니다.