LCA - 최소 공통 조상 찾기

최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘은 트리 구조 안에서 특정 정점 두 개의 공통 조상 정점 중 가장 가까운 공통 조상 정점을 찾는 알고리즘이다.

 

단순히 두 정점의 깊이를 맞춘 뒤 한 칸씩 동시에 올라가다가 마주치는 공통 조상이 최소 공통 조상인지라 쉽게 구할 수 있지만, 이동해야 할 정점이 많은 경우 희소 배열을 이용해 빠르게 최소 공통 조상을 구할 수 있다.

 

LCA

먼저, 7번 정점과 11번 정점의 공통 조상을 찾아보자.

 

 

7번 정점과 11번 정점이 공통으로 가지는 조상 정점은 1번 정점, 2번 정점, 4번 정점이 있다. 이 정점들은 모두 7번 정점과 11번 정점에서 시작해서 루트를 향해 올라가다가 마주칠 수 있는 공통되는 정점이다.

 

그 중에서도 시작 지점과 가장 가까운 최소 공통 조상은 4번 정점이다. 

 

이와 같은 방식으로 다른 정점들 사이의 최소 공통 조상을 구해보자.

4번 정점과 5번 정점의 최소 공통 조상은 2번 정점이다.

7번 정점과 5번 정점의 최소 공통 조상은 2번 정점이다.

2번 정점과 6번 정점의 최소 공통 조상은 1번 정점이다.

8번 정점과 9번 정점의 최소 공통 조상은 1번 정점이다.

 

이 과정을 코드로 구현하기 위해, 우리가 필요한 정보는 특정 정점의 부모 정점 번호, 특정 정점의 깊이이다. 루트 노드부터 깊이 우선 탐색을 진행한다.

 

n = 11

graph = [[] for _ in range(n+1)] # 가리키고 있는 자식 정점들
parent = [-1 for _ in range(n+1)] # 부모 정점의 번호
root = 1 # 루트 정점

graph[1] = [2, 3]
graph[2] = [4, 5]; graph[3] = [6];
graph[4] = [7, 8]; graph[6] = [9, 10];
graph[8] = [11]

depth = [0 for _ in range(n+1)] # DFS 를 시행하며 정점의 깊이를 저장
visited = [0 for _ in range(n+1)] # DFS 를 시행하며 정점 방문 여부 저장

def DFS(now, pre, dep):
  visited[now] = 1
  depth[now] = dep
  parent[now] = pre
  
  for next in graph[now]:
    if visited[next] == 0:
      DFS(next, now, dep + 1) # next 정점의 부모는 now, 깊이는 dep + 1

DFS(root, -1, 0) # 루트 정점의 부모는 -1, 깊이는 0

Depth :  [0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4]
Parent :  [-1, 1, 1, 2, 2, 3, 4, 4, 6, 6, 8]

 

 

특정 정점의 부모 정점 번호를 구했다면, 우리는 주어진 트리 구조를 다음과 같은 그래프로 보면서 역탐색이 가능하다. 이제 두 정점에서의 최소 공통 조상을 찾아보자.

 

def LCA(a, b):
  while depth[a] > depth[b]:
    a = parent[a]
  while depth[a] < depth[b]:
    b = parent[b]

  while a != b:
    a = parent[a]
    b = parent[b]

  return a

print(LCA(7, 11))

4

 

LCA 코드는 꽤나 간단하다. 먼저 탐색을 시작하는 두 정점의 깊이가 맞지 않다면 깊이가 더 깊은 정점을 동일한 깊이까지 맞춘 뒤, 두 정점이 도달하는 곳이 같아질 때 까지 동시에 부모 정점을 타고 올라간다. 시간 복잡도는 O(N) 이다.

 

LCA + Sparse Table

최소 공통 조상을 구해야 하는 그래프 안에서, 정점의 수가 많고 그리고 구해야 할 최소 공통 조상도 많다면 한 칸씩 올라가며 최소 공통 조상을 찾아가는 방식은 비효율적일 수 있다. 우리는 희소 배열을 이용해 탐색 시간을 줄일 것이다.

 

희소 배열에 대한 설명은 이 글에서 볼 수 있다.

https://readytojoin.tistory.com/entry/Sparse-Table-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4

Sparse Table - 희소 배열

 

# DFS 로 구한 부모 정점 번호 정보를 이용해,
# 부모 정점 방향으로 2^k 만큼 이동했을 때의 정점 번호를 저장한다.
DFS(root, -1, 0)

table = [[-1 for _ in range(n+1)] for _ in range(20)]

for i in range(1, n+1): 
  # 2^0 번 이동했을 때 : 1번 이동했을 때
  table[0][i] = parent[i]

for k in range(1, 20):
  for i in range(1, n+1):
  	# i에서 2^k 번 이동했을 때 : i에서 2^(k-1) 번 이동한 정점에서 2^(k-1) 번 이동
    table[k][i] = table[k-1][table[k-1][i]]

 

DFS 로 구한 부모 정점 번호 정보를 이용해 희소 배열을 만들어 2의 제곱꼴 횟수 만큼 이동했을 때의 정점 번호를 기록한다.

 

def LCA(a, b):
  if depth[a] > depth[b]:
    for i in range(19, -1, -1):
      if (depth[a] - depth[b]) >= (1 << i):
        a = table[i][a]
  elif depth[a] < depth[b]:
    for i in range(19, -1, -1):
      if (depth[b] - depth[a]) >= (1 << i):
        b = table[i][b]

  if a == b: return a
  else:
    for i in range(19, -1, -1):
      if table[i][a] != table[i][b]:
        a = table[i][a]
        b = table[i][b]
    return table[0][a]

print(LCA(7, 11))

 

Sparce Table 기법을 적용한 이 LCA 함수가 주요 포인트인데, 하나하나씩 살펴보자.

 

if depth[a] > depth[b]:
  for i in range(19, -1, -1):
    if (depth[a] - depth[b]) >= (1 << i):
      a = table[i][a]

 

먼저, 기존 LCA 함수에서 정점 a 와 정점 b 의 깊이가 맞지 않다면 깊이를 동일하게 맞춰주는 것 부터 시작한다. 이 코드는 정점 a 와 정점 b 의 깊이 차이가 (1 << i) 보다 크거나 같을 때 2^i 만큼 이동하는 코드인데, 2진수로 풀어서 보면 이해가 쉬울 것이다.

 

정점을 13번 이동한다고 가정해보자.

1 << i 를 큰 수부터 시작해서 하나씩 2진수 비트를 없애며 이동한다고 생각하면 이해하기 편리하다. 따라서 8 + 4 + 1 = 13 만큼 이동할 수 있다. 깊이 차만큼 이동해서 두 정점의 깊이를 동일하게 맞춘 뒤 한번에 같이 이동한다.

 

if a == b: return a
  else:
    for i in range(19, -1, -1):
      if table[i][a] != table[i][b]:
        a = table[i][a]
        b = table[i][b]
    return table[0][a]

 

깊이 차를 맞추고 두 정점이 동일하다면 해당 정점이 최소 공통 조상인 것이고, 그것이 아니라면 두 정점에서 2^i 번 이동한 정점이 같지 않을 때 계속 이동해야 한다. ( 2^i 번 이동한 정점이 같다면, 최소 공통 조상이거나 최소 공통 조상이 아닌 공통 조상일 수 있다. )

 

게속 이동하다보면 a와 b는 최소 공통 조상 바로 이전의 정점이 된다. if table[i][a] != table[i][b]: 로 인해 두 정점이 완전히 공통되지는 않기에, table[0][a] 를 통해 1번 더 이동한 결과를 반환한다.

 

---

출처

[Velog] 최소 공통 조상 알고리즘

최소 공통 조상 알고리즘