최소 공통 조상 (LCA, Lowest Common Ancestor)
최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.
위와 같은 예시 트리 구조에서, 13, 15번 정점의 최소 공통 조상은 5번 정점이 된다. 마찬가지로,
13, 11번 정점의 최소 공통 조상은 1번 정점(Root)이 된다.
LCA를 선형 탐색으로 구하기 : O(Depth)
트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까?
가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이다.
즉 Parent[x]를 정점 x의 부모 노드라 할 때, x = Parent[x] 연산을 반복하면 될 것이다
하지만 구하고자 하는 두 정점의 LEVEL(깊이)이 다르다면 문제가 발생한다.
11, 13번 정점의 최소 공통 조상을 찾는 상황을 생각해보자.
13번 정점에서 최소 공통 조상인 1번 정점까지는 4번을 거슬러 올라가야 하지만,
11번 정점에서는 3번을 거슬러 올라가면 도달할 수 있기 때문이다.
잠시 다른 예를 들어, 13번과 15번 정점의 최소 공통 조상을 구해보자. 최소 공통 조상은 5번 정점이다.
동시에 거슬러 올라간다면 원래 13번 정점을 가리키던 포인터가 5번 정점까지 도달한 순간,
원래 15번 정점을 가리키던 포인터는 2번 정점을 가리키게 된다.
따라서 동시에 거슬러 올라가기 전, 두 정점의 깊이를 동일하게 맞춰야 한다.
기본적인 최소 공통 조상(LCA) 알고리즘 코드
import sys
# 런타임 오류를 피하기
sys.setrecursionlimit(int(1e5))
n = int(input())
# 부모 노드 정보
parent = [0] * (n + 1)
# 각 노드까지의 깊이
d = [0] * (n + 1)
# 각 노드의 깊이가 계산되었는지 여부
c = [0] * (n + 1)
# 그래프(graph) 정보
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().spli())
graph[a].append[b]
graph[b].append[a]
# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
c[x] = True
d[x] = depth
for y in graph[x]:
# 이미 깊이를 구했다면 넘기기
if c[y]:
continue
parent[y] = x
dfs(y, depth + 1)
# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
# 먼저 깊이(depth)가 동일하도록
while d[a] != d[b]:
if d[a] > d[b]:
a = parent[a]
else:
b = parent[b]
# 노드가 같아지도록
while a != b:
a = parent[a]
b = parent[b]
return a
# 루트 노드는 1번 노드
dfs(1, 0)
m = int(input())
for i in range(m):
a, b = map(int, input().split())
print(lca(a, b))기본적인 기본적인 최소 공통 조상(LCA) 알고리즘 시간 복잡도
N=정점 갯수,M= 조상을 구할 두 노드의 쌍- 매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우
O(N)의 시간 복잡도가 요구됩니다. - 따라서 모든 쿼리를 처리할 때의 시간 복잡도는
0(NM)입니다
참고 블로그
https://velog.io/@juwon9733/%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81Lowest-Common-Acestor-LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-10%EB%B6%84-%EC%A0%95%EB%B3%B5
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/LCA(Lowest%20Common%20Ancestor).md
