트리 - 최소 공통 조상

최소 공통 조상은 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해

거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드입니다.

 

최소 공통 조상의 핵심 이론

일반적인 최소 공통 조상 구하기

1. 먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장합니다.

(탐색은 DFS 또는 BFS를 이용해 수행합니다.)

 

2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춥니다.

(두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료합니다.)

 

3. 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복합니다.

(처음 만나는 노드가 최소 공통 조상이 됩니다.)

 

위와 같은 방식을 이용하면 최소 공통 조상을 구할 수 있지만, 트리의 높이가 커질 경우 시간 제약 문제에 직면할 수 있습니다.

 

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

최소 공통 조상 빠르게 구하기의 핵심은 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서

2^k씩 올라가 비교하는 방식입니다.

(따라서 기존에 자신의 부모 노드만 저장하던 방식에서 2^k번째 위치의 부모 노드까지 저장해 둬야 합니다.)

 

1. 부모 노드 저장 리스트 만들기

부모 노드 리스트의 정의

P[K][N] = N번 노드의 2^k번째 부모의 노드 번호

 

부모 노드 리스트의 점화식

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

 

2. 선택된 두 노드의 깊이 맞추기

P 리스트를 이용해 기존에 한 단계씩 맞췄던 깊이를 2^k 단위로 넘어가면서 맞춥니다.

 

3. 최소 공통 조상 찾기

공통 조상을 찾는 작업 역시 한 단계씩이 아닌 2^k단위로 점프하면서 맞춥니다.

(K 값을 1씩 감소하면서 P 리스트를 이용해 최초로 두 노드의 부모가 달라지는 값을 찾습니다.)