LCA(lowest common ancestor)
트리에서 임의의 두 노드를 선택했을 때
두 노드가 각각 자신을 포함해
거슬러 올라가 부모 노드를 탐색할 때
처음 공통으로 만나게 되는 부모 노드
탐색은 DFS나 BFS를 이용
1. 일반적인 LCA 구하기
트리를 만들 때 각 노드의
부모 노드와 깊이를 저장
a) 선택된 두 노드의 깊이가 다른 경우
더 깊은 노드의 노드를 부모 노드로 오려주면서
같은 깊이로 맞춘다.
b) 깊이가 같은 경우
동시에 부모 노드로 올라가면서
두 노드가 같은 노드가 될 때까지 반복
이 때 처음 만나는 노드가 LCA
이 방식을 이용하면 구할 수 있지만!
트리의 높이가 크면 시간이 오래 걸린다.
2. 빠르게 LCA 구하기 with DP
서로의 깊이를 맞춰주거나
같아지는 노드를 찾을 때
2^k 씩 올라가 비교한다!
2^k 번째 위치의 부모 노드까지 저장하고 시작
배열을 만들 때 k 구하기
트리의 깊이 > 2^k
Bottom-Up 방식
즉, k = 0 (첫 번째 부모)는
다 채우고 시작.
부모 노드 배열
P[k][n] -> n번 노드의 2^k 번째 부모의 노드 번호
점화식
P[k][n] = P[k-1][P[k-1][n]]
k = 4이면
N의 16번째 부모 노드는
N의 8번째 부모 노드의 8번째 부모 노드
테이블을 다 채웠다면
1. 깊이 맞추기
깊이를 2^k 단위로 넘어가며 맞춰준다.
예를 들어, 깊이 차이가 x이라면
2^k <= x을 만족하면서 k가 최대가 되는 만큼
이동하며 높이 차이가 0일 때까지 반복.
2. LCA 찾기
이 역시도 2^k 단위로 올라간다.
k 값을 1씩 감소하면서 테이블을 이용해
최초로 두 노드의 부모가 달라지는 k를 찾는다.