최소 공통 조상 (Lowest Common Ancestor / LCA)
정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점
정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점
위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다.
최소 공통 조상 구하기
- 선형 탐색 : \(O(depth) = O(N)\)
1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다.
2. 최소 공통 조상을 찾을 두 정점을 확인한다.
3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다.
4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하나씩 올라가 최소 공통 조상을 찾는다.
- 이분 탐색 : \(O(log(depth)) = O(logN)\)
위의 선형 탐색의 1번에서 각 정점의 부모뿐만 아니라 \(2^k\) 번째 조상까지 저장한다.
이제 부모 노드로 거슬러가는 과정을 2의 제곱수만큼 한 번에 건너뛸 수 있다.
parent[k][v] = parent[k - 1][parent[k - 1][v]]
(parent[k][v] : 정점 v의 \(2^k\) 번째 조상 정점 번호)
728x90
반응형
'알고리즘 > 그래프' 카테고리의 다른 글
| [CS] 단절점 (0) | 2023.04.12 |
|---|---|
| [백준] 11438번 LCA 2 (JAVA) (0) | 2023.03.31 |
| [백준] 1922번 네트워크 연결 (JAVA) (0) | 2023.03.30 |
| [백준] 1197번 최소 스패닝 트리 (JAVA) (0) | 2023.03.30 |
| [CS] 최소 신장 트리와 구현 알고리즘 (JAVA) (0) | 2023.03.29 |
