기본적인 최소 공통 조상(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)