최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)

최소 공통 조상 빠르게 구하기

• 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식
• 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2ᵏ번째 위치의 부모 노드까지 저장해 둬야함

원리

1. 부모 노드 저장 리스트 만들기

• 부모 노드 리스트 정의 : P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드 번호

내 바로 위에 있는 부모 노드뿐만 아니라, 내 자리에서 2ᵏ 칸 위에 있는 부모가 누군지 저장해놔야함

• 부모 노드 리스트의 점화식 :  P[K][N] = P[K-1][P[k-1][N]]

예시)
K = 2 N=12 가정

P[2][12] = P[1][P[1][12]]

P[2][12] : 12번 노드의 2²번째 부모 = 1
P[1][12] = 12번 노드의 2¹번째 부모 = 6
P[1][P[1][12]] = (12번 노드의 2¹번째 부모 = 6)의 2¹번째 부모 = 1
 ➔ P[2][12] = P[1][P[1][12]] = P[1][P[0][P[0][12]]]

 ➔ N의 4번째 부모 노드는 N의 2번째 부모 노드의 2번째 부모노드라는 의미

• 리스트에서 K는 '트리의 깊이 > 2ᵏ'를 만족하는 최댓값

트리의 높이가 100일 때 N의 102번째 부모노드?  ➔ 없음 

예시 트리의 최대 깊이는 5
트리의 깊이 > 2ᵏ ➔ 5 > 2² ➔ K=2

즉, 이 트리의 모든 노드는 2³번째 부모 노드를 지니고 있는 경우는 없음

K \ index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0		1	1	2	2	3	3	4	4	6	6	11	11	13	13
1				1	1	1	1	2	2	3	3	6	6	11	11
2												1	1	3	3

 

2. 선택된 두 노드의 깊이 맞추기

노드 2와 노드 15의 깊이 맞추기 
노드2의 깊이 : 2, 노드 15의 깊이 : 6
두 노드의 깊이차이 : 4
깊이를 맞추기 위해 더 깊이 있는 노드 15의 4번째 부모 노드를 P 리스트를 이용해 찾음 
4 = 2²이므로 K=2이고, P[2][15] = 3이므로 노드 3으로 이동


높이차이가 2048이라면
기존 한 칸씩 이동하는 LCA 알고리즘 ➔ 2048칸 올라가기
제곱수 LCA ➔ 2048 = 2¹¹이므로 11칸 올라가기

 

3. 최소 공통 조상 찾기

• 2ᵏ 단위로 점프하면서 맞춤
• K값을 1씩 감소하면서 P리스트를 이용해 최초로 두 노드의 부모가 달라지는 값 찾음  

 

[11438번] 최소 공통 조상 구하기