최소공통조상(LCA)

LCA란?

최소 공통 조상(Lowest Common Ancestor) 줄여서 LCA로 불리는 이 알고리즘은 트리에서 두 정점이 가지고 있는 가장 가까운 공통 조상을 찾는 알고리즘 입니다.

 

위와 같은 그래프가 있을 때 6번 정점과 9번 정점의 최소 공통 조상은 3번 입니다. 우리는 눈으로 바로 3번이 최소 공통 조상이라는 것을 찾을 수 있지만 알고리즘으로 이를 찾으려면 쉽지 않습니다. 어떻게 찾을 수 있을지 한번 생각해 보고 다음을 읽어보시기 바랍니다.

알고리즘 이해하기

최소 공통 조상을 찾는 방법은 하나씩 자신의 부모를 타고 올라가다가 공통으로 만나는 첫 번째 정점을 찾는 것입니다.

8번과 9번의 최소 공통 조상을 찾는다고 해보겠습니다. 두 정점의 부모를 찾아 올라갑니다. 먼저 8의 부모인 5와 9의 부모 7이 됩니다.

 

 

아직 공통 조상이 없기 때문에 또 위로 올라갑니다. 5의 부모 2와 7의 부모 3을 찾습니다.

아직 최소 공통 조상이 없기 때문에 또 위로 올라갑니다. 그럼 둘 다 1이라는 최소 공통 조상을 찾게 됩니다.

 

쉽게 최소 공통 조상을 찾았지만 문제가 항상 이렇게 쉽지만은 않습니다. 가령 처음 예제였던 6과 9의 최소 공통 조상을 찾아보겠습니다.

6의 부모 3과 9의 부모 7을 찾았습니다. 최소 공통 조상이 없기 때문에 한 단계 올라가 봅니다.

 

3의 부모는 1이고 7의 부모는 3 입니다. 아직 공통 조상이 없기 때문에 계속 위를 찾게 됩니다. 최소 공통 조상이 3이지만 그냥 위로 타고 올라가기만 한다면 최소 공통 조상을 지나치게 될 수 있습니다. 이는 정점들의 깊이를 고려하지 않았기 때문입니다. 두 정점이 같은 높이에서 한 칸씩 위로 올라가야 공통 조상을 찾을 수 있습니다.

6은 깊이가 2이고, 9는 깊이가 3이기 때문에 두 깊이를 맞춰주기 위해 9만 부모를 찾아 올라갑니다. 그럼 7이라는 부모를 찾을 수 있고, 6과 7의 깊이가 같음을 알 수 있습니다. 이제 둘 다 한 칸 위로 올라갑니다.

이렇게 6과 7의 부모가 3이라는 것을 알 수 있습니다.

알고리즘 이해하기

1. 두 정점의 깊이를 같게 만들어 줍니다.
2. 한 칸씩 부모 정점으로 이동하여 같은 정점이 나올때까지 반복합니다.
3. 처음으로 만나는 같은 정점이 최소 공통 조상이 됩니다.

이렇게 최소 공통 조상을 찾을 수 있습니다. 문제를 풀면서 이해해 보도록 하겠습니다. 

2023.10.10 - [분류 전체보기] - [백준 11437] LCA

[백준 11437] LCA