Lowest Common Ancestor

기본 방법

 

-

루트 노드에서 BFS or DFS를 시작해,

각 노드의 부모 노드와 깊이를 저장

 

- 

깊이가 다른 경우

더 깊은 노드의 부모 노드를 1개씩 올려주면서 

같은 깊이로 맞춤

 

*PipeLine

만약 두 노드가 같게 나온다면, 해당 노드가 LCA이므로 탐색 종료

 

-

깊이가 맞춰진 상태에서 

동시에 부모 노드로 올라가면서 누 노드가 같아질 때까지 반복

if (2 !== 3) > 시행

 

 

최소 공통 조상 빠르게 구하기

 

-

깊이를 맞춰 주거나, 부모 노드로 한 단계씩 올라갈때

한 단계 > 2^k 씩 올라가 비교하는 방법

 

-

기존 부모 노드만 저장해 두던 방식에서

2^k번째 위치의 부모 노드도 추가로 저장할 것

 

-

P[K][N]

N번 노드의 2^K번째 부모 노드 번호

 

-

점화식

P[K][N] = P[K-1][P[k-1][N]]

 

N번 노드의 2^K번째 부모 노드는, N의 2^(K-1)번째 부모 노드의 2^(K-1)번째 부모 노드

K가 16일 때, 8번째 부모 노드의 8번째 부모 노드