Colin's Blog
[c++] 부분 트리의 깊이(Subtree Depth)

이번에는 부분 트리(Subtree)의 깊이(Depth)에 대해 알아보겠습니다. 트리(Tree) 자료구조에서 부분 트리는 어떤 한 노드를 루트로 하는 서브트리와 같습니다. 즉, 루트 노드와 그 노드의 자식 노드들이 해당하는 부분 트리입니다. 이 글에서는 깊이 우선 탐색(Depth-First Search, DFS)을 사용하여 부분 트리의 깊이를 계산하는 방법을 살펴보겠습니다.

깊이 우선 탐색(Depth-First Search, DFS)

깊이 우선 탐색은 루트 노드로부터 시작하여 한 노드에서 아래로 가능한 한 깊숙히 탐색한 후, 더 이상 탐색할 수 없을 때 올라오는 방식의 탐색 알고리즘입니다. 이 알고리즘은 스택(Stack)이나 재귀 함수를 사용하여 구현할 수 있습니다. 여기서는 재귀 함수를 사용한 방법을 설명하겠습니다.

void DFS(int node, int depth) {
    // 현재 노드의 깊이를 계산하거나 처리

    for (int next : adj[node]) {
        DFS(next, depth + 1);
    }
}

위의 예시 코드에서 DFS 함수는 현재 노드와 해당 노드의 깊이를 입력으로 받습니다. 그리고 해당 노드의 자식 노드들을 순회하면서 각각의 자식 노드에 대해 DFS 함수를 재귀적으로 호출합니다. 각 자식 노드의 깊이는 부모 노드의 깊이에서 1을 더한 값이 됩니다.

부분 트리의 깊이 계산

부분 트리의 깊이를 계산하기 위해서는 부분 트리의 루트 노드와 해당 노드의 깊이를 입력으로 DFS 함수를 호출하면 됩니다. 이렇게 하면 해당 노드를 루트로 하는 부분 트리의 깊이를 계산할 수 있습니다.

예를 들어, 다음은 그래프의 인접 리스트 표현과 DFS 함수를 사용하여 특정한 노드의 부분 트리의 깊이를 계산하는 예시 코드입니다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj; // 그래프의 인접 리스트
vector<bool> visited;    // 방문한 노드인지를 나타내는 배열

void DFS(int node, int depth) {
    // 현재 노드의 깊이를 계산하거나 처리

    for (int next : adj[node]) {
        DFS(next, depth + 1);
    }
}

int main() {
    int n; // 노드의 개수
    int root; // 부분 트리의 루트 노드
    // 그래프 입력 및 초기화
    
    visited = vector<bool>(n, false); // 모든 노드를 방문하지 않은 상태로 초기화
    
    int rootDepth = 0; // 루트 노드의 깊이 확인
    DFS(root, rootDepth); // 루트 노드로 시작하여 깊이 우선 탐색 수행
}

결론

이렇게 부분 트리의 깊이를 계산하는 방법을 알아보았습니다. 깊이 우선 탐색(DFS)을 사용하여 부분 트리의 루트 노드와 해당 노드의 깊이를 입력으로 넣어주면 간단하게 부분 트리의 깊이를 계산할 수 있습니다.

부분 트리의 깊이를 계산하는 것은 그래프 이론과 알고리즘에서 매우 중요한 개념 중 하나이므로, 익숙해지도록 연습해보시기를 권장합니다.

참고 문헌

© 2018 Colin. All rights reserved.