최소 공통 조상

정의

• 트리에서 임의의 두 노드 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 시 처음 공통으로 만나게 되는 부모 노드

• 트리에서 두 노드 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드
• 두 노드 u, v와 최소공통조상인 노드 사이의 경로를 이어보면 두 노드 u, v 사이의 최단 경로가 됨

특징

• 최소공통조상을 구하는 방식은 일반적인 방식과 빠르게 구하는 방식이 있음
• 일반적인 방식은 트리의 높이가 크지 않을 때 씀 (데이터가 많지 않아 시간 제한이 타이트하지 않을 때)

과정 (일반적인 방식)

1. 루트 노드부터 탐색을 시작해서 각 노드의 부모 노드와 깊이를 저장
• 트리라서 바로 직전 탐색 노드가 부모 노드가 됨
• 트리라서 depth 구하는 게 가능함

2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춰줌. 이때, 두 노드가 같으면 해당 노드가 최소공통조상이므로 탐색 종료
• ex) 3과 15 노드라면, 3에서 깊이가 같아지고 두 노드가 같기에 최소공통조상은 3

3. 깊이가 같은 상태에선 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복함. 이때, 처음 만나는 노드가 최소공통조상

과정 (빠르게 구하는 방식)

• 정의) 서로의 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식(일반적인 방식)에서 단계씩 올라가 비교하는 방식으로 변경한 것

• 특징) 기존에 자신의 부모 노드만 저장해 놓던 방식(일반적인 방식)과 달리 번째 위치의 부모 노드까지 저장해 둬야함

1. 부모 노드 저장 배열 만들기
1. 부모 노드 배열의 정의: P[K][N] = N번 노드의 번째 부모의 노드 번호
2. 부모 노드 배열의 점화식: 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 = 트리의 깊이 > 만족하는 최대값
3. 점화식 이용해 배열 값 채우기
• 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. 최소공통조상 찾기 (깊이를 한 단계씩이 아닌 단위로 넘어가면서 맞춤)
1. K값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달리지는 값 찾음
2. 최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동
3. K가 0이 될 때까지 a, b를 반복
4. 반복 종료된 후 두 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소공통조상이 됨
• ex) 14와 15 최소공통조상 찾기

• ex) 16과 16 최소공통조상 찾기

 

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main