안녕하세요 이번 시간에는 최소 공통 조상(LCA)에 대해 알아보는 시간을 갖도록 하겠습니다.
최소 공통 조상이란 트리에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드입니다.
최소 공통 조상을 구하는 방법은 다음과 같습니다.
- 트리 구현 : 주어진 노드들의 연관관계로 트리를 구현합니다.
- 루트 노드에서 탐색하여 각 노드의 부모 노드와의 깊이 저장 : dfs 또는 bfs를 이용하여 부모 및 깊이 배열을 초기화합니다.
- 최소 공통 조상 찾기
3-1. 선택된 두 노드의 깊이가 다른 경우 깊이가 더 깊은 노드를 부모 노드로 올려주면서 같은 깊이로 맞춤
3-2. 깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복, 이 때 처음 만나는 노드가 최소 공통 조상
최소 공통 조상을 백준 11437(LCA) 문제로 구현해보겠습니다. N개의 정점으로 이루어진 트리가 있을 때 주어진 두 노드의 가장 가까운 공통 조상이 몇 번인지를 구하는 문제입니다. 위에서 주어진 조건을 하나씩 구현해나가면 됩니다.
import java.util.*;
import java.io.*;
class Main{
static List<Integer>[] tree;
static int[] depth, parent;
static boolean[] check;
static int N,M;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// 1. 트리 구현
tree = new List[N+1];
for(int i=1;i<=N;i++) tree[i] = new ArrayList<>();
for(int i=0;i<N-1;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
tree[s].add(e);
tree[e].add(s);
}
// 2. 루트 노드에서 탐색하여 각 노드의 부모 노드와의 깊이 저장
depth = new int[N+1];
parent = new int[N+1];
check = new boolean[N+1];
bfs(1);
// 3. 최소 공통 조상 찾기 시작
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0;i<M;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 정의한 함수에서 a의 깊이가 크거나 같기 때문에 b의 깊이가 더 클 경우 순서 바꿔서 대입
if(depth[a] < depth[b]) sb.append(lca(b,a)).append("\n");
else sb.append(lca(a,b)).append("\n");
}
System.out.println(sb);
}
static int lca(int a, int b){
// 선택된 두 노드의 깊이가 다른 경우 깊이가 더 깊은 노드를 부모 노드로 올려주면서 같은 깊이로 맞춤
while(depth[a] != depth[b]) a = parent[a];
// 깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복
// 이 때 처음 만나는 노드가 최소 공통 조상
while(a != b){
a = parent[a];
b = parent[b];
}
return a;
}
static void bfs(int node){
check[node] = true;
Queue<Integer> queue = new ArrayDeque<>();
queue.add(node);
int level = 1;
int size = 1;
int cnt = 0;
while(!queue.isEmpty()){
int curr = queue.poll();
for(int next : tree[curr]){
if(!check[next]){
check[next] = true;
queue.add(next);
// 탐색하면서 다음 노드가 현재 노드의 자식 노드이기 때문에 부모 및 깊이 배열에 해당 값 추가
parent[next] = curr;
depth[next] = level;
}
}
// 현재 레벨에서의 탐색이 끝나면 다음 레벨로 넘어가기
cnt++;
if(cnt == size){
cnt = 0;
size = queue.size();
level++;
}
}
}
}최소 공통 조상을 더 빠르게 구하는 방법이 있습니다. 바로 DP를 이용하여 하나의 노드가 가질 수 있는 모든 부모들을 저장하는 것입니다.
위의 방식과 차이점은 점화식을 이용하여 모든 부모 노드들을 저장하는 것입니다. P[k][n] = n번 노드의 2^k번째 부모의 노드 번호로 정의한 후 P[k][n] = p[k-1]p[k-1][n]]로 나머지 부모들을 채워나갑니다.
여기서 주의할 점은 부모 배열이 1차원에서 2차원으로 바뀌게 되면서 부모 배열 초기화 및 탐색 방법이 변경된다는 점입니다. DFS 또는 BFS로 탐색할 때 부모 자식 관계는 1단계, 즉 2^0단계이므로 k=0을 대입하여 값을 추가하며 최소 공통 조상을 탐색할 때 최대 K값을 기준으로 k가 0이 될때까지 감소시키면서 모든 K에 대한 노드들의 부모를 탐색하여 값을 조정합니다.
이를 백준 11438(LCA2)로 구현해보겠습니다.
import java.util.*;
import java.io.*;
class Main{
static List<Integer>[] tree;
static int[] depth;
// 이차원 배열로 부모 노드 저장 배열 생성
// parent[k][n] = n번 노드의 2^k번째 부모의 노드 번호
// parent[k][n] = parent[k-1][parent[k-1][n]]
static int[][] parent;
static boolean[] check;
static int N,M,K;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// 1. 트리 구현
tree = new List[N+1];
for(int i=1;i<=N;i++) tree[i] = new ArrayList<>();
for(int i=0;i<N-1;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
tree[s].add(e);
tree[e].add(s);
}
// 2. K의 최댓값 구하기 : 트리의 깊이 > 2^k를 만족하는 최댓값
// 즉 현재 노드의 2^k번째 부모를 부모 배열에 다 저장, 이렇게 하면 하나의 노드에 대한 모든 부모를 알 수 있음
int tmp = 1;
K = 0;
while(tmp <= N){
tmp <<= 1;
K++;
}
// 3. 루트 노드에서 탐색하여 각 노드의 부모 노드와의 깊이 저장
depth = new int[N+1];
parent = new int[K+1][N+1];
check = new boolean[N+1];
bfs(1);
// 4. 부모 배열 점화식에 맞게 BFS에서 탐색하지 못한 부분 초기화
for(int k=1;k<=K;k++){
for(int n=1;n<=N;n++){
parent[k][n] = parent[k-1][parent[k-1][n]];
}
}
// 5. 최소 공통 조상 찾기 시작
M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0;i<M;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 정의한 함수에서 b의 깊이가 크거나 같기 때문에 a의 깊이가 더 클 경우 순서 바꿔서 대입
if(depth[a] > depth[b]) sb.append(lca(b,a)).append("\n");
else sb.append(lca(a,b)).append("\n");
}
System.out.println(sb);
}
static int lca(int a, int b){
// K를 기준으로 두 노드의 깊이를 같게 맞춰줌
// 선택된 두 노드의 깊이의 차가 2^k 보다 크거나 같을 경우, 즉 두 노드의 깊이가 서로 다를 경우
// 현재 k의 노드의 부모의 깊이가 다른 노드의 깊이보다 크다면 해당 노드를 부모 노드로 올려줌
for(int k=K;k>=0;k--){
if(Math.pow(2,k) <= depth[b] - depth[a]){
if(depth[a] <= depth[parent[k][b]]) b = parent[k][b];
}
}
// K를 기준으로 현재 K일 때의 최소 공통 조상 구하기
// 깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복
// 이 때 가장 큰 K값에서 a와 b가 같을 때가 최소 공통 조상
for(int k=K;k>=0;k--){
if(parent[k][a] != parent[k][b]){
a = parent[k][a];
b = parent[k][b];
}
}
// a와 b가 다를 경우 바로 위의 부모를 구하기
if(a != b) return parent[0][a];
else return a;
}
static void bfs(int node){
check[node] = true;
Queue<Integer> queue = new ArrayDeque<>();
queue.add(node);
int level = 1;
int size = 1;
int cnt = 0;
while(!queue.isEmpty()){
int curr = queue.poll();
for(int next : tree[curr]){
if(!check[next]){
check[next] = true;
queue.add(next);
// 탐색하면서 다음 노드가 현재 노드의 자식 노드이기 때문에 부모 및 깊이 배열에 해당 값 추가
// 이 때 부모 - 자식 관계는 1단계, 즉 2^0단계이므로 k=0을 대입
parent[0][next] = curr;
depth[next] = level;
}
}
// 현재 레벨에서의 탐색이 끝나면 다음 레벨로 넘어가기
cnt++;
if(cnt == size){
cnt = 0;
size = queue.size();
level++;
}
}
}
}
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.