[Algorithm] - LCA ( 최소 공통 조상 )

LCA ( Lowest Common Ancestor )

---

최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.

• 아래 그림에서 노드 13번과 15번 노드의 공통 조상을 찾는다한다.
• 따라 올라가게 되면 5번 노드가 공통 조상이다.

• 아래 그림에서 노드 13번과 11번 노드의 공통 조상을 찾는다한다.
• 따라 올라가게 되면 1번 노드가 공통 조상이다.

알고리즘

1. a,b 노드의 깊이를 파악한다.

2. 깊이가 동일하다면 상위 노드를 찾아가면서 동일한 노드가 나올 때까지 추적

 

그렇다면 노드의 깊이를 어떻게 파악할 것인가?

• DFS로 root 노드로 부터 깊이를 미리 구해둔다. 
• 또한, 깊이를 구하면서 자신의 부모 노드를 기억하여 두고 부모 노드로 추적할 수 있게끔 할 수 있어야한다.
• 결국 Depth , Parent , Visited , Graphs 4개가 필요한 것이다.

 

BOJ 11437

• LCA 문제인 BOJ 11437번을 푼 과정입니다. 참고

def dfs(start,level):
    visited[start]=1
    depth[start]=level

    for move in graphs[start]:
        if not visited[move] :
            parent[move]=start
            visited[move]=1
            depth[move]=level+1
            dfs(move,level+1)
            
def lca(a,b):
    # level check
    while depth[a] != depth[b]:
        if depth[a]<depth[b]:
            b=parent[b]
        else:
            a=parent[a]
    # 상위 Node 탐색
    while a!=b:
        a , b = parent[a] , parent[b]
    return a