[백준 11438 C++] LCA 2

오늘은 백준(BOJ) 11438번 LCA2 문제에 대해 다뤄보도록 하겠습니다.

LCA2 문제 링크 (백준(BOJ) 11438번 문제): https://www.acmicpc.net/problem/11438

11438번: LCA 2

 

혹시나 LCA 알고리즘에 대해 모르고 있다면 아래 링크를 참조하시기 바랍니다. 

[LCA(Lowest Common Ancestor) Algorithm]

 

문제 설명 

백준 11438번 LCA 2 문제는 트리를 구성하기 위해 노드에 대한 정보가 주어지고, 다음으로 주어지는 두 노드의 최소 공통 조상을 구하는 문제입니다. 이 문제는 11437번 LCA 문제와는 다르게 노드의 개수도 많아졌음에도 불구하고 시간제한이 1.5초로 걸려있습니다. 

 

문제 풀이 

백준 11438번 LCA 문제의 핵심은 최소 공통 조상을 찾기 위해 거꾸로 올라갈 때, 시간 복잡도 O(NM)이 아닌 O(NlogM)를 사용해야 합니다. 그럼, 어떻게 하면 O(NlogM)만에 최소 공통 조상을 구할 수 있을까요? 

 

그것은 바로 조상을 찾으려고 할 때, 2의 제곱 수 씩 거꾸로 올라가 주면 됩니다. 자세히 와닿지 않는다면 아래 그래프를 통해 이해해보도록 합시다. 

트리

위와 같은 그래프가 존재한다고 가정해봅시다. 이때, 노드 10의 조상에 대해 알아봅시다. 노드 10의 조상은 1, 2, 5, 9가 된다는 것을 알 수 있습니다. 여기서 주목할 부분은 9, 5, 1 이런 식으로 첫 번째 조상, 두 번째 조상, 네 번째 조상. 즉, 2의 제곱 수 씩 거꾸로 올라감으로 최소 공통 조상을 찾는다는 것입니다. 이와 같은 접근을 사용하게 되면, 시간 복잡도 O(NlogM)만에 최소 공통 조상을 구할 수 있게 됩니다. 

(단, 시간을 줄이는 만큼, 메모리 공간을 많이 쓰게 됩니다.)

 

알고리즘 원리 

1. DFS (깊이 우선 탐색)을 통해 각 노드의 깊이(Depth)를 계산하고 부모(Parent) 노드를 찾습니다.

2. 다이나믹 프로그래밍(Dynamic programming) 방식을 이용하여 각 노드마다 2의 제곱 수인 조상을 저장해줍니다. 

3. 최소 공통 조상을 찾을 두 노드를 입력 받은 경우 (찾을 때 까지 반복)

   3-1. 깊이(Depth)가 낮은 노드를 기준으로 하여 두 노드의 깊이(Depth)가 동일할 때까지 2의 제곱 수 씩 거꾸로 올라가줍니다. 

   3-2. (3-1)과정을 거친 후, 두 노드가 동일하면 최소 공통 조상을 찾은 것으로 해당 노드를 반환해줍니다. (끝)

4. 두 노드의 깊이(Depth)가 같을 경우, 두 노드의 부모가 같아질 때까지 2의 제곱 수 씩 거꾸로 올라가줍니다. 

5. 최소 공통 조상인 노드를 반환 해줍니다. 

 

이를 코드로 나타내면 아래와 같이 나타낼 수 있습니다.