이진 트리(binary tree)가 주어졌을 때, 루트(root)에서 리프(leaf)에 이르는 여러 경로 중 가장 짧은 경로를 찾아 출력하는 프로그램을 작성해 보겠습니다.
트리는 왼쪽에서 오른쪽으로 순회하기 때문에, 최단 경로가 여러 개 존재할 경우에는 트리의 왼쪽에서 가장 먼저 탐색되는 경로를 출력하게 됩니다.
여기서 핵심 아이디어는 큐(queue)를 이용한 레벨 순서 순회(Level Order Traversal)입니다. 큐로 각 레벨을 차례대로 탐색하면 가장 적은 레벨 수로 도달하는 리프 노드, 즉 루트에서 리프까지의 최단 경로를 자연스럽게 얻을 수 있습니다.
위 트리에서 루트에서 리프까지 이어지는 경로는 다음과 같습니다.
10 -> 3 (모든 경로 중 가장 짧은 경로)
10 -> 211 -> 100
10 -> 211 -> 146
예제
입력 : 10 3 211 100 146
출력 : 10 3
알고리즘
1단계 – 노드 구조체 정의
왼쪽·오른쪽 자식 포인터(left, right)와 데이터(data)를 멤버로 갖는 node 구조체를 선언합니다.
2단계 – 노드 생성 함수
newnode(int data) 함수는 새 노드를 동적 할당하고, data를 저장한 뒤 left와 right를 NULL로 초기화하여 반환합니다.
3단계 – 경로 출력 함수
path(int data, unordered_map<int,int> prnt) 함수는 부모 정보를 담은 맵(prnt)을 재귀적으로 거슬러 올라가며 루트부터 현재 노드까지의 경로를 출력합니다. prnt[data] == data라면 루트에 도달한 것이므로 재귀를 종료합니다.
4단계 – 최단(왼쪽) 경로 탐색 함수
left(Node* root) 함수가 핵심 로직입니다.
- STL 큐(queue<Node*>)에 루트를 삽입합니다.
- unordered_map<int,int>에 루트의 부모를 자기 자신으로 기록합니다.
- 큐가 빌 때까지 반복하면서 노드를 하나씩 꺼내 좌우 자식을 큐에 삽입하고, 부모 정보를 맵에 저장합니다.
- 좌우 자식이 모두 없는 노드(리프)를 처음 만나면 그 값을 leaf에 저장하고 반복을 종료합니다.
- path(leaf, prnt)로 루트까지의 경로를 출력한 뒤 마지막으로 leaf를 출력합니다.
5단계 – main() 함수
main()에서 트리를 구성한 뒤 left(root)를 호출하고 프로그램을 종료합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체
struct Node {
struct Node *left,*right;
int data;
};
// 새 노드 생성 함수
Node* newnode(int data){
Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// 경로를 출력하는 함수
void path(int data, unordered_map <int,int> prnt) {
if (prnt[data] == data)
return;
path(prnt[data], prnt);
cout << prnt[data] << " ";
}
// 리프 경로를 찾는 함수
void left(Node* root) {
queue<Node*> que;
que.push(root);
int leaf = -1;
Node* temp = NULL;
unordered_map<int, int> prnt;
prnt[root->data] = root->data;
while (!que.empty()){
temp = que.front();
que.pop();
if (!temp->left && !temp->right){
leaf = temp->data;
break;
} else {
if (temp->left){
que.push(temp->left);
prnt[temp->left->data] = temp->data;
}
if (temp->right){
que.push(temp->right);
prnt[temp->right->data] = temp->data;
}
}
}
path(leaf, prnt);
cout << leaf << " ";
}
int main(){
Node* root = newnode(90);
root->left = newnode(21);
root->right = newnode(32);
root->left->left = newnode(45);
root->right->left = newnode(52);
root->right->right = newnode(27);
root->left->left->left = newnode(109);
root->left->left->right = newnode(101);
root->right->right->left = newnode(78);
left(root);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
90 32 52
레벨 순회 과정을 살펴보면, 루트 90을 먼저 방문한 뒤 자식 노드인 21과 32를 큐에 삽입합니다. 이후 21의 하위 트리를 지나 32의 자식 노드인 52에 도달하는 순간, 52가 처음 만나는 리프 노드가 됩니다. 따라서 90 → 32 → 52가 루트에서 리프까지의 최단 경로로 출력됩니다.