Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이진 트리 최대 굽힘 경로 길이 찾기

이진 트리가 주어졌을 때 굽힘(bend)의 개수가 가장 많은 경로를 찾아 그 길이를 출력하는 문제를 함께 해결해 보겠습니다. 여기서 굽힘이란 경로의 진행 방향이 왼쪽에서 오른쪽으로, 또는 오른쪽에서 왼쪽으로 바뀌는 지점을 의미합니다.

문제 예시

입력 −

C++로 구현하는 이진 트리 최대 굽힘 경로 길이 찾기

출력 −

6

이 접근 방식에서는 트리를 순회하면서 직전 이동 방향을 계속 추적합니다. 방향이 바뀌는 순간마다 굽힘 카운트를 갱신하고, 모든 경로를 탐색한 뒤 그중 최댓값을 구합니다.

문제 해결 접근 방법

트리의 모든 경로를 하나씩 순회하면서 각 경로에서 발생한 굽힘의 개수를 세고, 기존 정답보다 크면 정답을 갱신하는 방식입니다. 구체적인 동작 흐름은 다음과 같습니다.

  • 루트에서 시작해 왼쪽 자식이 있으면 방향 'l'로, 오른쪽 자식이 있으면 방향 'r'로 탐색을 시작합니다.
  • 같은 방향으로 계속 내려가면 굽힘 수는 그대로 유지되고, 방향이 바뀌면 굽힘 수가 1 증가합니다.
  • 리프 노드에 도달하면 지금까지의 굽힘 수와 현재 최댓값을 비교하여 필요하면 정답과 경로 길이를 갱신합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
struct Node { // 노드 구조체 정의
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key){ // 새 노드 생성 및 초기화
    struct Node* node = new Node();
    node->left = NULL;
    node->right = NULL;
    node->key = key;
    return node;
}
void maximumBends(struct Node* node,char direction, int bends,
                    int* maxBends, int soFar,int* len){
    if (node == NULL) // NULL에 도달한 경우
       return;
    if (node->left == NULL && node->right == NULL) { // 리프 노드에 도달하면
                                                         // 정답을 갱신할지 확인한다
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    }
    else {
        if (direction == 'l') { // 현재 방향이 왼쪽인 경우
            maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // 방향이 바뀌므로 굽힘 수 증가
        }
        else {
            maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // 방향이 왼쪽일 때와 동일한 로직
        }
    }
}
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);
    int len = 0, bends = 0, maxBends = -1;
    if(!root) // 트리가 비어 있는 경우
       cout << "0\n";
    else{
        if (root->left) // 왼쪽 서브트리가 존재하면
            maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
        if (root->right) // 오른쪽 서브트리가 존재하면
            maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

실행 결과

4

코드 설명

위 코드는 트리의 모든 경로를 재귀적으로 순회하면서 지금까지 발견한 굽힘의 개수를 누적합니다. 경로의 끝, 즉 리프 노드에 도달하면 그때까지의 굽힘 수가 이전 최댓값보다 큰지 검사하고, 조건이 참이라면 최대 굽힘 수와 함께 경로의 길이도 새로운 값으로 갱신합니다. 이 과정을 모든 경로에 대해 반복하면 프로그램은 최종적으로 굽힘이 가장 많은 경로의 길이를 출력하게 됩니다.

시간 복잡도

루트에서 각 노드로 가는 경로는 유일하므로 모든 노드를 정확히 한 번씩 방문하게 되며, 따라서 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 노드 수입니다.

마무리

이번 튜토리얼에서는 굽힘의 개수가 최대인 경로의 길이를 찾는 문제를 해결했습니다. DFS 순회를 활용한 전체 접근 방식과 C++ 구현 코드를 살펴보았으며, 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.