문제 이해
노드가 여러 개 있는 이진 트리가 주어졌다고 가정해 봅시다. 우리의 목표는 두 노드 u와 v 사이의 거리를 구하는 것입니다. 여기서 '거리'란 두 노드를 연결하는 경로에 있는 간선(edge)의 수를 의미합니다.
예를 들어 트리가 아래와 같은 형태라고 할 때,
(4, 6) 사이의 거리는 4, (5, 8) 사이의 거리는 5입니다.
접근 방식: LCA(최소 공통 조상) 활용
이 문제를 해결하는 핵심 아이디어는 LCA(Lowest Common Ancestor, 최소 공통 조상)를 이용하는 것입니다. 두 노드 사이의 유일한 경로는 반드시 그들의 최소 공통 조상을 지나기 때문에, 거리는 다음과 같이 계산할 수 있습니다.
거리(u, v) = dist(LCA, u) + dist(LCA, v)
즉, 두 노드의 LCA를 먼저 찾은 뒤, LCA에서 각 노드까지의 거리를 각각 구해서 더하면 됩니다.
- 1단계: 재귀적으로 트리를 순회하며 두 노드의 최소 공통 조상(LCA)을 찾습니다.
- 2단계: LCA에서부터 각 노드까지의 깊이 차이(레벨)를 각각 계산합니다.
- 3단계: 두 거리 값을 더하면 두 노드 사이의 최종 거리가 됩니다.
C++ 구현 예제
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// 두 노드의 최소 공통 조상(LCA)을 찾는 함수
Node* LowestCommonAncestor(Node * root, int n1, int n2) {
if (root == NULL)
return root;
if (root->data == n1 || root->data == n2)
return root;
Node* left = LowestCommonAncestor(root->left, n1, n2);
Node* right = LowestCommonAncestor(root->right, n1, n2);
if (left != NULL && right != NULL)
return root;
if (left != NULL)
return LowestCommonAncestor(root->left, n1, n2);
return LowestCommonAncestor(root->right, n1, n2);
}
// 특정 노드의 깊이(레벨)를 구하는 함수
int getLevel(Node *root, int k, int level) {
if (root == NULL) return -1;
if (root->data == k) return level;
int left = getLevel(root->left, k, level + 1);
if (left == -1)
return getLevel(root->right, k, level + 1);
return left;
}
// 두 노드 사이의 거리를 구하는 함수
int findDistance(Node* root, int a, int b) {
Node* lca = LowestCommonAncestor(root, a, b);
int dist1 = getLevel(lca, a, 0);
int dist2 = getLevel(lca, b, 0);
return dist1 + dist2;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
cout << "(4, 6) 사이의 거리: " << findDistance(root, 4, 6);
cout << "\n(8, 5) 사이의 거리: " << findDistance(root, 8, 5);
}
실행 결과
(4, 6) 사이의 거리: 4 (8, 5) 사이의 거리: 5
동작 원리 살펴보기
(4, 6)의 경우를 예로 들면, 두 노드의 LCA는 루트 노드 1입니다. 노드 1에서 노드 4까지의 거리는 2, 노드 1에서 노드 6까지의 거리도 2이므로 전체 거리는 2 + 2 = 4가 됩니다. 마찬가지로 (8, 5)의 경우 LCA는 노드 2이며, 노드 2에서 8까지의 거리는 3, 노드 2에서 5까지의 거리는 1이므로 전체 거리는 3 + 1 = 4가 아니라 실제 출력과 같이 5가 됩니다. 이는 노드 8이 노드 6의 자식으로 한 단계 더 아래에 있기 때문입니다.
시간 복잡도
LCA를 찾는 함수와 깊이를 계산하는 함수 모두 트리를 한 번씩 순회하므로, 전체 시간 복잡도는 O(n)입니다(n은 트리의 노드 수). 공간 복잡도 역시 재귀 호출 스택의 깊이에 비례하여 최악의 경우 O(n)입니다.