정의
•
트리에서 임의의 두 노드 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 시 처음 공통으로 만나게 되는 부모 노드
•
트리에서 두 노드 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드
◦
두 노드 u, v와 최소공통조상인 노드 사이의 경로를 이어보면 두 노드 u, v 사이의 최단 경로가 됨
특징
•
최소공통조상을 구하는 방식은 일반적인 방식과 빠르게 구하는 방식이 있음
◦
일반적인 방식은 트리의 높이가 크지 않을 때 씀 (데이터가 많지 않아 시간 제한이 타이트하지 않을 때)
과정 (일반적인 방식)
1.
루트 노드부터 탐색을 시작해서 각 노드의 부모 노드와 깊이를 저장
•
트리라서 바로 직전 탐색 노드가 부모 노드가 됨
•
트리라서 depth 구하는 게 가능함
2.
선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춰줌. 이때, 두 노드가 같으면 해당 노드가 최소공통조상이므로 탐색 종료
•
ex) 3과 15 노드라면, 3에서 깊이가 같아지고 두 노드가 같기에 최소공통조상은 3
3.
깊이가 같은 상태에선 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복함. 이때, 처음 만나는 노드가 최소공통조상
과정 (빠르게 구하는 방식)
•
정의) 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식(일반적인 방식)에서 단계씩 올라가 비교하는 방식으로 변경한 것
•
특징) 기존에 자신의 부모 노드만 저장해 놓던 방식(일반적인 방식)과 달리 번째 위치의 부모 노드까지 저장해 둬야함
1.
부모 노드 저장 배열 만들기
a.
부모 노드 배열의 정의: P[K][N] = N번 노드의 번째 부모의 노드 번호
b.
부모 노드 배열의 점화식: P[K][N] = P[K-1][P[K-1][N]]
•
N번 노드의 번째 부모 노드 = N번 노드의 번째 부모 노드의 번째 부모 노드
◦
ex) P[3][10]
▪
P[3][10] = 10번 노드의 번째 부모 노드
•
P[3][10] = P[2][P[2][10]] = (10번 노드의 번째 부모 노드)의 번째 부모 노드
▪
P[2][10] = 10번 노드의 번째 부모 노드
•
P[2][10] = P[1][P[1][10]] = (10번 노드의 번째 부모 노드)의 번째 부모 노드
▪
P[1][10] = 10번 노드의 번째 부모 노드
•
P[1][10] = P[0][P[0][10]] = (10번 노드의 번째 부모 노드)의 번째 부모 노드
▪
P[3][10]
= P[2][P[2][10]]
= P[2][P[1][P[1][10]]]
= P[2][P[1][P[0][P[0][10]]]]
◦
ex) P[3][10]
▪
10의 번째 부모 = 10의 번째 부모의 번째 부모
▪
10의 번째 부모 = 10의 번째 부모의 번째 부모
▪
10의 번째 부모 = 10의 번째 부모의 번째 부모
▪
10의 8번째 부모
= 10의 4번째 부모의 4번째 부모
= [10의 2번째 부모의 2번째 부모]의 4번째 부모
= [(10의 1번째 부모의 1번째 부모)의 2번째 부모]의 4번째 부모
•
K = 트리의 깊이 > 만족하는 최대값
c.
점화식 이용해 배열 값 채우기
•
K=0 (초기값): 일반적인 최소공통조상 구하는 것과 마찬가지로 dfs/bfs로 탐색해서 채움
•
K=1, 2: 점화식으로 채움
◦
ex) P[2][14]
▪
P[2][14] → 14의 4번째 부모
= P[1][P[1][14]] → 14의 2번째 부모의 2번째 부모
= P[1][P[0][P[0][14]]] → 14의 1번째 부모의 1번째 부모의 2번째 부모
⇒ P[0][14] (14의 1번째 부모)는 초기값으로 알고 있음
▪
P[2][14]
•
P[0][14] = 13
•
P[1][14] = P[0][P[0][14]] = P[0][13] = 11
•
P[2][14] = P[1][P[1][14]] = P[1][11] = P[0][P[0][11]] = P[0][6] = 3
2.
선택된 두 노드의 깊이 맞추기 (깊이를 한 단계씩이 아닌 단위로 넘어가면서 맞춤)
•
ex) 2와 15 깊이 맞추기
◦
깊이 차이 : → K = 2
◦
부모: P[2][15] 로 찾아감 (15의 4번째 부모 노드)
3.
최소공통조상 찾기 (깊이를 한 단계씩이 아닌 단위로 넘어가면서 맞춤)
a.
K값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달리지는 값 찾음
b.
최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동
c.
K가 0이 될 때까지 a, b를 반복
d.
반복 종료된 후 두 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소공통조상이 됨
•
ex) 14와 15 최소공통조상 찾기
•
ex) 16과 16 최소공통조상 찾기
참고