트리(Tree) | 최소 공통 조상 Lowest Common Ancestor (알고리즘) 정리

LCA의 기본적인 접근법에 대해 먼저 소개해 보고, 빠른 접근 방법을 정리해보겠다.

최소 공통 조상 (Lowest Common Ancestor)

LCA | 최소 공통 조상

• 트리 그래프에서 임의의 두 노드가 거슬러 올라가다가 처음 공통으로 만나는 ‘최소 공통 부모 노드’를 탐색하는 알고리즘이다.

[1] 일반적인 방법론 (1칸 씩 점프하여 구하는 방식)

→ 이 방식은 시간 제한이 타이트 하지 않을 때 활용하면 된다.

과정 설명

1) 데이터 초기화하기

• a) tree를 인접 리스트로 구현하여 입력값 세팅해준다.
• b) DFS나 BFS로 각 노드의 (부모노드, 현재 깊이)를 세팅해준다.

2) 질의 처리하기

• (1) 더 깊이 큰 노드를 a에 swap 시킴
• (2) 깊이 더 큰 a 의 깊이가 b의 깊이와 같아질 때까지 parent로 거슬러 올라감
• (3) 동일한 깊이에서 a와 b가 같아질 때까지 동시에 한칸씩 거슬러 올라감

→ 최종적으로 같아진 LCA 리턴하면 된다.

---

[2] 빠르게 구하는 방법론 (2^k칸 씩 점프하여 빠르게 LCA 구하는 방식)

→ 이 방식은 시간 제한이 타이트할 때 최적화 된 방법으로 활용하면 된다.

→ DP 개념도 활용해서, parent[k][n] 에 대한 값을 정의해준다. 각 n 노드에 대한 2^k 번째 부모 노드를 저장하는 2차원 배열이다.

과정 설명

1) 데이터 초기화하기

• a) tree를 인접 리스트로 구현하여 세팅, 최대 깊이 가능한 2^k만족할 kmax도 구해준다.
• b) DFS나 BFS로 각 노드의 (부모노드) 는 parent[0][k] 에 세팅해주고, 깊이는 depth[n]에 세팅
• c) 2중 for문 돌면서 kmax까지 모든 노드들에 대한 2^k번쨰 부모노드를 DP 점화식 활용하여 세팅해준다.

//점화식
parent[k][n] = parent[k-1][parent[k-1][n]];

//즉, n번쨰 노드의 2^k 번째 위 부모 노드는
  n번째 노드의 2^k-1번쨰 부모노드의 2^k-1번째 부모노드와 같다.

ex) k = 2 이라 치자.
n의 2^2 = 4번쨰 부모 노드 = n의 2^1 = 2 번째 부모노드의 2^1 = 2 번째 부모노드이다.

2) 질의 처리하기

• (1) 더 큰 깊이 노드를 b 기준으로 swap
• (2) 깊이 같아지도록 b를 a의 깊이까지 2^k씩 점프시켜 올림

for(int k=kmax; k>=0; k--){
		if(Math.pow(2, k) <= depth[b] - depth[a] ) {
			if(depth[a] <= depth[ parent[k][b] ] ){
				//b가 2^k씩 점프해서 올라간 게 a의 깊이보다 크거나 같을 때까지 
				b = parent[k][b]; //거슬러 올라감 
}

• (3) 같아진 깊이에서 a, b 모두를 동시에 2^k씩 점프시켜 올림

for(int k=kmax; k>=0; k--){
	//두 노드 동시에 2^k씩 올려보냄 단, 다를 때까지만 쭉
	if(parent[k][a] != parent[k][b]) {
			a = parent[k][a];
			b = parent[k][b];
  }
}