📌 최소공통조상(LCA)
- 트리 그래프에서 임의의 두 노드를 선택했을 떄 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음으로 공통으로 만나게되는 부모노드를 말함
◾ 일반적인 최소공통조상 구하기
- 트리의 높이가 크지 않을 때 사용
- 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장
-
탐색은 DFS 또는 BFS를 이용해 수행
→ 트리라는 특징 때문에 바로 직전 탐색 노드가 부모노드가 되며, 탐색을하면서 depth 구하기 가능
-
선택된 두 노드의 깊이가 다를 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춘다. 이때, 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료
-
노드의 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복
→ 부모노드 찾아서 올라가기
- 일반적인 최소공통조상 찾기 방법은 트리의 높이가 커질 경우 시간 제약 문제 발생
