[Algorithm] LCA 알고리즘

 

LCA는 "Lowest Common Ancestor" 가장 가까운 공통 조상을 찾는 알고리즘이다.

 

 

백준 3584번을 풀면서 이해해보장

www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

 

 

해당 트리에서 3번과 2번의 가장 가까운 공통 조상은 10번이라는 것을 바로 알 수 있다.

그렇다면 a와b가 주어졌을 때 알고리즘으로 최소 공통 조상을 찾아보자.

 

Rule

📌 a의 조상을 모두 찾아 리스트로 만든다.

📌 b의 조상을 모두 찾아 리스트로 만든다. (a,b의 마지막 리스트는 root다.)

📌 두 리스트 모두 root에서 시작해 서로 다른 값이 나올 때 까지 index-1 한다.

📌 서로 다른 값이 나오면  index+1 에 있는 값이 최소 공통 조상이다.

ex) a=3, b=2 일 때

a_parents = [3, 16, 10, 4, 8]

b_parents = [2, 10, 4, 8]

마지막 값이 다를 때 a는 16을 b는 2를 가리키고 있다. index+1하면 둘 다 10을 가리킨다.

그러므로 3과 2의 공통 조상은 10이다.

 

 

Code

import sys

t=int(sys.stdin.readline())
for case in range(t):
    n=int(sys.stdin.readline())
    parents=[0 for x in range(n+1)]
    for i in range(n-1):
        a,b=map(int, sys.stdin.readline().split())
        parents[b]=a

    a,b=map(int, sys.stdin.readline().split())
    a_parents=[a]
    b_parents=[b]
    #a의 조상 찾기
    while parents[a]:
        a_parents.append(parents[a])
        a=parents[a]
    #b의 조상 찾기
    while parents[b]:
        b_parents.append(parents[b])
        b=parents[b]
    
    #마지막 값이 root이므로 끝에서 부터 시작
    a_spot=len(a_parents)-1
    b_spot=len(b_parents)-1
    while a_parents[a_spot]==b_parents[b_spot]:
        a_spot-=1
        b_spot-=1

    print(a_parents[a_spot+1])