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

최소 공통 조상(Lowest Common Ancestor, LCA)

---

최소 공통 조상(Lowest Common Ancestor, LCA) 란?

최소 공통 조상(LCA) 란 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘 이다. 즉 두 정점이 만나는 최초 부모 정점을 찾는 것을 의미한다. 

 

 

 

 

 

 

---

최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘

 

• 모든 노드에 대한 깊이(Depth)를 계산한다.
• 최소 공통 조상을 찾을 두 노드를 확인한다.
  • 먼저 두 노드의 깊이(Depth)가 동일 하도록 거슬러 올라간다.
  • 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.
• 최소 공통 조상을 찾을 두 노드를 확인한다. 

---

LCA 알고리즘 풀이 이해 

 

 

1. 각 노드의 "Depth" 정보를 저장한다.
    0  →  1(Root)
    1  →  2, 3
    2 →  4,5,6,7'


2. 각 노드의 "Parent 정보" 를 저장해 둔다.
    Parent = [0, 1, 1, 2, 2, 3, 3,]

3.  두 정점의 "Depth" 비교 
    (1)  if  (Depth 가 일치)
          →  if  (두 노드의 Parent 일치) : LCA 찾음(종료)
          →  else  : 두 노드를 자신의 Parent 노드 값으로 변경
                             ex) a = parent[a]
                                    b = parent[b]
    (2) else:(Depth 가 불 일치)
           Depth가 더 깊은 노드를 해당 노드의 Parent 노드로 변경(Depth 가 감소)
           ex) if depth[a] > depth[b]:
                      a = parent[a]
                 else: 
                     b = parent[b]

---

코드(Python)

 

11437번: LCA

 

 

import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정

n = int(input())

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

for _ in range(n - 1):
    a, b = map(int, input().split())
    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

dfs(1, 0) # 루트 노드는 1번 노드

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

 

* 참고

 

[알고리즘] DFS/BFS