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

 

 

1.  개념

     

     최소 공통 조상 : 트리에서 임의의 두 노드가 처음 공통으로 갖게 되는 조상 노드

          

 

 

2.  구현

       

      < 1 >  일반적인 최소 공통 조상 구하기

                

                일반적인 방법은 트리의 높이가 별로 높지 않을 때 이용한다.

                

                1 )  부모 노드, 깊이 리스트 생성 

                 트리의 루트 노드에서 탐색을 시작하여 각 노드의 부모 노드와 깊이를 저장한다.

                 이때 탐색은 DFS 혹은 BFS를 이용한다.

                  

                2 ) 깊이 맞추기

                 더 깊은 노드를 부모 노드로 올려 깊이를 맞춰준다.

                 깊이를 맞춰주었을 때 두 노드가 서로 같으면 해당 노드가 최소 공통 조상이 된다.

                  

                3 ) 최소 조상 노드 찾기

                 깊이가 같아진 두 노드를 함께 부모 노드로 올려준다.

                 두 노드가 서로 같아질 때까지 반복한다.

                 두 노드가 서로 같아지면 해당 노드가 최소 공통 조상이 된다.

               

                하지만 이 방법은 시간 제약에 약하기 때문에 좀 더 빠르게 계산할 수 있는 방법을 알아야 한다.

 

 

      < 2 >  최소 공통 조상 빠르게 구하기

                

                위에서 이용했던 방식을 그대로 가져가되 부모 노드로 한 단계씩 올려주는 것이 아니라

                2ᵏ번째 조상 노드로 올려주면 된다.

                

                1 )  부모 노드 저장 리스트 생성

                부모 노드 저장 리스트의 크기는 K × N으로 

                N은 노드의 개수를 의미하며

                K는 트리의 깊이 > 2ᴷ 를 만족하는 K의 최댓값으로 정한다.

 

                 부모 노드 저장 리스트 P에서 P[k][n]는 n번 노드의 2ᵏ번째 조상을 의미한다. 

                 부모 노드 저장 리스트를 생성할 땐 아래 점화식을 이용하면 된다.

                 P[k][n] = P[k-1][P[k-1][n]]

                 

                2 )  선택된 두 노드의 깊이 맞추기

                 더 깊은 노드를 (두 노드의 깊이 차이)번째 조상으로 올려준다.

                

                3 )  최소 공통 조상 찾기

                 두 노드에 대하여 P[K][n]에서 출발하여 K값을 1씩 감소하면서

                 두 노드의 부모 노드가 서로 달라지는 시점으로 두 노드를 옮겨준다.

                 

                 마지막으로 최초로 부모 노드가 달라진 두 노드의 부모 노드를 찾아서 이동해주면 된다.

                 

                  

 

3.  문제

 

# 1  최소 공통 조상 구하기 1 - 백준 11437번

https://www.acmicpc.net/problem/11437

11437번: LCA

 

 

import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write

n = int(input())
tree = [[] for _ in range(n+1)]

# 트리 생성 -> 인접리스트
for _ in range(0, n-1):
    s, e = map(int, input().split())
    tree[s].append(e)
    tree[e].append(s)

# 부모, 깊이 리스트 생성 -> BFS
depth = [0] * (n+1)
parent = [0] * (n+1)
visited = [False] * (n+1)


def BFS(node):
    queue = deque()
    queue.append(node)
    visited[node] = True
    level = 1        # 깊이
    now_size = 1     # 현재 깊이에서의 트리 크기
    count = 0        
    while queue:
        now_node = queue.popleft()
        # now_node : 현재 노드(부모 노드) / next : now_node의 자식 노드들
        for next in tree[now_node]:
            if not visited[next]:
                visited[next] = True
                queue.append(next)
                parent[next] = now_node    # 부모 노드 저장
                depth[next] = level        # 깊이 저장
        count += 1
        
        # 현재 깊이에 존재하는 노드 탐색이 끝나면
        if count == now_size:
            count = 0
            # 큐에 들어가있는 노드(now_node의 자식 노드) 개수 = 다음 깊이의 트리 크기
            now_size = len(queue)
            # 깊이 갱신
            level += 1


BFS(1)    # BFS에 루트 노드 전달


def executeLCA(a, b):
    # 깊이 맞춰주기
    if depth[a] < depth[b]:
        a, b = b, a
    while depth[a] != depth[b]:
        a = parent[a]
    
    # 최소 공통 조상 찾기
    while a != b:
        a = parent[a]
        b = parent[b]
    
    return a

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(str(executeLCA(a, b)))
    print("\n")

 

 

 

# 2  최소 공통 조상 구하기 2 - 백준 11438번

https://www.acmicpc.net/problem/11438

11438번: LCA 2