Lowest Common Ancestor(LCA)는 트리 구조에서 특정한 두 노드의 공통 조상 중 가장 가까운 조상을 뜻한다.
희소 테이블을 공부한 적 있다면 매우 유사한 방식으로 진행된다.
LCA풀이는 다음의 순서로 진행된다.
1. dfs로 모든 노드의 깊이, 부모를 체크한다. 여기서 부모는 바로 위 직속 부모를 말한다.
2. 위의 결과를 이용해서 모든 노드의 2**i번째 부모를 찾아 그 결과를 저장한다.
3. 두 노드가 주어지면 둘 중 더 깊은 노드를 두 노드의 깊이가 같아질 때까지 거슬러 올려보낸다.
4. 최상단 노드부터 내려오며 두 노드의 공통 부모를 찾는다.
문제로 바로 알아보자.
https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
전체 코드 보기
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
n = int(input())
graph = collections.defaultdict(list)
for _ in range(n - 1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
h = [0 for _ in range(n+1)]
for i in range(2, n+1):
h[i] = h[i>>1] + 1
height = h[-1]
d = [0 for _ in range(n)] # depth table
parent = [[0 for _ in range(n)] for _ in range(height+1)]
visited = [False for _ in range(n)]
def dfs(node, depth):
d[node - 1] = depth
for next in graph[node]:
if not visited[next - 1]:
visited[next - 1] = True
parent[0][next - 1] = node
dfs(next, depth + 1)
start = 1
visited[start - 1] = True
dfs(start, 0)
# set parents
for i in range(1, h[-1] + 1):
for j in range(n):
mid = parent[i - 1][j]
parent[i][j] = parent[i - 1][mid - 1]
# LCA
def lca(a, b):
# 깊이가 더 깊은 노드를 a로 만들어주기
if d[a - 1] < d[b - 1]:
a, b = b, a
# 같은 깊이로 맞추기
diff = d[a - 1] - d[b - 1]
for i in range(height, -1, -1):
if diff & (1 << i):
diff -= (1 << i)
a = parent[i][a - 1]
if a == b:
return a
# 위에서부터 내려오며 LCA 찾기
for i in range(height, -1, -1):
if parent[i][a - 1] != parent[i][b - 1]:
a = parent[i][a - 1]
b = parent[i][b - 1]
return parent[0][a - 1]
m = int(input())
for _ in range(m):
x, y = map(int, input().split())
print(lca(x, y))
하나씩 코드를 살펴보자.
0. 준비하기
아래의 코드는 height = [logN]으로 설정해준다. 예를 들어 N=5일때 height = 2이고 N= 16이면 height=4이다.
이 height는 2차원 배열 parent의 행 개수를 설정하는데 도움이 된다.
h = [0 for _ in range(n+1)]
for i in range(2, n+1):
h[i] = h[i>>1] + 1
height = h[-1]
1. dfs로 모든 노드의 깊이, 부모를 체크
d = [0 for _ in range(n)] # depth table
parent = [[0 for _ in range(n)] for _ in range(height+1)]
visited = [False for _ in range(n)]
def dfs(node, depth):
d[node-1] = depth # 깊이 체크
for next in graph[node]:
if not visited[next - 1]:
visited[next - 1] = True
parent[0][next - 1] = node # 부모 체크
dfs(next, depth + 1)
start = 1
visited[start - 1] = True
dfs(start, 0)
2. parent 배열 만들기
# set parents
for i in range(1, height + 1):
for j in range(n):
mid = parent[i - 1][j]
parent[i][j] = parent[i - 1][mid - 1]
3. LCA 함수 작성
# LCA
def lca(a, b):
# 깊이가 더 깊은 노드를 a로 만들어주기
if d[a - 1] < d[b - 1]:
a, b = b, a
# 같은 깊이로 맞추기
diff = d[a - 1] - d[b - 1]
for i in range(height, -1, -1):
if diff & (1 << i):
diff -= (1 << i)
a = parent[i][a - 1]
if a == b:
return a
# 위에서부터 내려오며 LCA 찾기
for i in range(height, -1, -1):
if parent[i][a - 1] != parent[i][b - 1]:
a = parent[i][a - 1]
b = parent[i][b - 1]
return parent[0][a - 1]# 같은 깊이로 맞추기
만약 a가 b에 비해 depth가 7만큼 더 깊다고 하자.
7은 이진수 표현으로 111(2)이다. 따라서 7= 4+2+1임을 쉽게 알아낼 수 있다.
그러므로 a가 b와 같은 높이가 되기 위해서는 4칸 점프, 2칸 점프, 1칸 점프를 해주면 된다.
# 위에서부터 내려오며 LCA 찾기
a, b는 이제 같은 depth로 설정되어있다. 이제 반복문을 돌며 LCA를 찾아낸다. 코드를 보면 i는 height부터 시작해서 0이 될때까지 1씩 줄어든다. 그때마다 parent[i][a - 1]와 parent[i][b - 1]가 같은지 살펴본다.
예를 들어 height = 2이라면 먼저 parent[2][a - 1]와 parent[2][b - 1]를 살핀다. 이는 a의 2**2만큼 떨어져있는 부모와 b의 2**2만큼 떨어져있는 부모가 같은 지를 비교하는 것이다.
그래서 만약 같다면? => 공통 조상이긴 한데, 더 가까운 공통 조상이 있을 수 있으므로 i값을 내려서 더 탐색 진행
만약 다르다면? => 노드를 크게 크게 건너뛰기 때문에 LCA를 지나쳤을 수 있다. a와 b를 지금 탐색 노드로 옮김
댓글