본 강좌에서는 C++ 프로그래밍을 이용해 최소 공통 조상(Lowest Common Ancestor, LCA)을 구하는 문제를 다룹니다.
최소 공통 조상은 두 노드의 조상이면서 두 조상 중 가장 깊은 노드를 의미합니다. 이 문제는 트리 자료구조와 깊이 우선 탐색(DFS)을 이해하는 데 유용합니다.
문제 설명
트리가 주어질 때, 두 노드 A와 B의 최소 공통 조상을 구하는 문제를 해결해야 합니다.
트리는 비어 있지 않으며, 중복된 노드는 없다고 가정합니다. 노드의 번호는 1부터 시작합니다.
입력 형식
N A B 에서 N은 노드의 수, A와 B는 최소 공통 조상을 찾을 두 노드입니다. 트리는 다음과 같이 주어집니다. 부모 노드와 자식 노드로 이루어진 M개의 줄이 주어지며, 각 줄은 'P C' 형식으로 부모 P와 자식 C를 나타냅니다.
출력 형식
두 노드 A와 B의 최소 공통 조상의 노드 번호를 출력합니다.
예제
입력
7 4 5 4 6 5 3 6 2 1 4 1 7
출력
4
문제 분석
주어진 예제에서 트리는 다음과 같이 나타낼 수 있습니다:
1
/ \
4 7
/ \
5 6
/ \
3 2
노드 A(5)와 B(3)의 최상위 부모인 4가 최소 공통 조상입니다.
만약 노드 A와 B가 동일한 경우, 그 노드 자체가 최소 공통 조상이 됩니다.
알고리즘 접근법
최소 공통 조상을 찾기 위해 다양한 알고리즘이 존재하지만, 여기에서는 깊이 우선 탐색(DFS)와 부모 노드 추적 방식을 이용한 방법을 설명하겠습니다.
1. 트리 구조 저장
먼저 인접 리스트를 사용하여 트리를 저장하겠습니다. 부모 노드를 알고 있다면 자식 노드를 리스트에 추가하는 방식으로 트리를 구성합니다.
2. DFS를 통한 깊이 저장
각 노드의 깊이를 저장하고, 노드의 부모를 추적하여 LCA를 찾는 방법입니다.
각 노드에 대해 탐색하면서 깊이를 기록하고, 부모 노드도 함께 저장합니다.
3. LCA 구하기
두 노드 A와 B의 깊이를 비교하여 깊이가 얕은 노드를 올리면서 부모 노드를 추적합니다.
두 노드가 같아지면 그 노드가 LCA입니다.
C++ 코드 구현
다음은 C++를 사용한 알고리즘 코드입니다:
#include
#include
#include
using namespace std;
vector tree[100001];
int parent[100001];
int depth[100001];
// DFS를 통한 깊이와 부모 저장
void dfs(int node, int par, int dep) {
parent[node] = par;
depth[node] = dep;
for (int child : tree[node]) {
if (child != par) {
dfs(child, node, dep + 1);
}
}
}
// 두 노드의 LCA 구하기
int findLCA(int a, int b) {
// 깊이 맞추기
while (depth[a] > depth[b]) {
a = parent[a];
}
while (depth[b] > depth[a]) {
b = parent[b];
}
// LCA 찾기
while (a != b) {
a = parent[a];
b = parent[b];
}
return a;
}
int main() {
int N;
cin >> N;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
// DFS로 깊이와 부모 정보 저장
dfs(1, 0, 0);
int A, B;
cin >> A >> B;
cout << findLCA(A, B) << endl;
return 0;
}
코드 설명
1. 트리 표현
주어진 입력에 따라 트리를 인접 리스트 형태로 표현합니다.
각각의 부모-자식 관계를 저장하여 나중에 DFS 동안 참조할 수 있도록 합니다.
2. DFS 함수
dfs 함수는 현재 노드, 부모 노드, 깊이를 입력받아, 해당 노드의 부모와 깊이를 저장하고 순회합니다.
자식 노드는 부모와 동일하지 않을 때만 탐색합니다.
3. LCA 함수
두 노드의 깊이를 조정한 뒤, 부모를 타고 올라가며 두 노드가 같아지는 지점을 찾습니다.
이 지점이 바로 최소 공통 조상입니다.
결론
이번 강좌에서는 최소 공통 조상 문제의 개념, 접근법 및 C++ 구현을 살펴보았습니다.
이 문제는 트리 자료구조의 기본 개념을 이해하는 데 매우 유용하며, 다양한 응용 문제에서도 자주 등장합니다.
알고리즘 문제 해결 능력을 기르기 위해 다각도로 이 문제를 풀어보시기 바랍니다.