[알고리즘] 최소 공통 조상(Lowest Common Ancestor)

📌 최소 공통 조상(Lowest Common Ancestor) 예제 문제를 기준으로 설명(BOJ 11437번)

• N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 있다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며 루트 노드의 번호는 1번이다.
  두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하자.

기본적인 최소 공통 조상(LCA) 알고리즘 설계 방법
①. 모든 노드에 대한 깊이(depth)를 계산한다. (by DFS)
②. 최소 공통 조상을 찾을 두 노드를 확인한다.

• 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다.
• 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.

③. 모든 LCA(a, b) 연산에 대하여 ②번의 과정을 반복한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)	# 최대 깊이 설정

n = int(input())

parent = [0] * (n+1)			# 부모 노드의 정보
depth = [0] * (n+1)				# 각 노드까지의 깊이 정보
c = [0] * (n+1)					# 각 노드까지의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
	a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)

# 루트 노드부터 시작하여 깊이를 구해주는 DFS함수
def DFS(x, depth):
	c[x] = True
    depth[x] = depth
    for i in graph[x]:
    	# 깊이를 구했다면 그냥 넘기기
    	if c[i]:
        	continue
# 예를 들어 x = 1이고 이와 인접한 노드의 번호가 2, 3번이라고 가정하자.
# 노드 2, 3번의 부모 노드의 번호는 1번이므로 parent[2] = 1, parent[3] = 1로 생각한다면 이해가 빠를 것이다.
# 인접 노드를 전부 돌아봤다면 깊이를 1만큼 증가시키고 다시 탐색한다.
        parent[i] = x
        DFS(i, depth+1)

def LCA(a, b):
# 예를 들어 a = 8이고 b = 15라고 가정해보자.
# 15번 노드의 깊이가 4로 8번 노드의 깊이보다 1만큼 크므로 조건문을 실행하게 된다면 15번 노드의 부모 노드인 11번 노드가 되며 두 노드의 깊이는 동일해진다.
# 그 다음 공통 조상의 노드가 같아질 때까지 위로 거슬러 올라가는데 8 → 4 → 2가 되고 11 → 5 → 2가 되어 최소 공통 조상으로 2가 출력된다.
	# 먼저 깊이가 동일하도록
	while depth[a] != depth[b]:
    	if depth[a] > depth[b]:
    		a = parent[a]
    	else:
    		b = parent[b]
    # 노드가 같아지도록
   	while a != b:
    	a = parent[a]
        b = parent[b]
    return a

DFS(1, 0)

n = int(input())
for _ in range(n):
	a, b = map(int, input().strip().split())
    LCA(a, b)