가장 가까운 공통 조상(Lowest Common Ancestor, LCA)
Lowst Common Ancestor LCA. 흔히 줄여서 LCA로 씁니다.
가장 가까운 공통 조상 알고리즘은 그리 흔하게 쓰이는 알고리즘은 아닙니다. 다만, 알고 있다면 해당 문제를 풀 때 수월하게 풀 수 있는 알고리즘이죠.
해당 알고리즘도 탐색 알고리즘에 속합니다. (사실 탐색 알고리즘이 아닌 게 있나?)
사실 제한 시간이 타이트하게 잡혀있는 문제라면, 해당 알고리즘을 모른다면 풀 수 없게 설계할 수 있는 알고리즘 문제이기도 합니다.
어떤 문제에 쓰이나?
제목에서 유추할 수 있듯이 트리 구조에서 두 노드의 가장 가까운 공통 조상을 찾기 위해 쓰입니다.
해당 알고리즘을 쓰기 위해선, 전제 조건이 반듯이 하나 필요합니다.
바로 루트 노드를 알고 있어야 한다는 것.
만약, 루트 노드가 정해져 있지 않았을 경우 해당 알고리즘은 사용할 수 없습니다.
루트 노드를 찾고 알고리즘을 사용하거나 혹은 다른 방식으로 문제를 풀어야 합니다.
(사실 루트 노드가 정해져 있지 않다면, 찾는 과정에서 해당 문제를 푸는 것 이상으로 시간을 사용할 수도 있습니다.)
사용법
가장 가까운 공통 조상을 찾는 방법은 아래와 같습니다.
•
아래의 알고리즘을 위해, 최상위 노드를 안다고 가정합니다.
1.
모든 노드에 대해 깊이를 찾고 저장합니다. (최상위 노드 부터, 차례대로 계산됩니다.)
2.
가장 가까운 공통 조상을 찾기 위한 두 노드를 설정합니다.
3.
두 노드 중 더 높은 깊이의 노드를 더 낮은 노드의 깊이와 동일하도록 부모의 노드로 변경합니다.
4.
두 노드의 깊이가 같아졌다면, 해당 노드의 부모가 같아질 때까지 두 노드를 부모로 계속해서 갱신합니다.
아래의 그림으로 설명을 해보겠습니다.
현재 5의 노드와, 8의 공통 조상을 찾으려합니다.
•
5와 8의 깊이를 같게 합니다.
더 깊이가 깊은 노드인 8 → 4로 이동.
•
4,5의 깊이가 같은지 확인 후, 같다면 현재 조상이 같은 지를 확인합니다.
4,5는 다름. → 4,5의 다음 부모 노드로 이동
•
2,2 같은 노드까지 도달했습니다. 그러므로 8,5의 가장 가까운 공통 조상은 2입니다.
기본 코드
아래 코드는 LCA를 찾기 위해 직관적으로 나타낸 코드입니다.
var nodeCount = int.Parse(sr.ReadLine());
var nodeParent = new int[nodeCount + 1];
var nodeDepth = new int[nodeCount + 1];
var nodeCheck = new bool[nodeCount + 1];
var board = new List<List<int>>();
for (var b = 0; b < nodeCount; b++)
{
board.Add(new List<int>());
}
for (var n = 0; n < nodeCount; n++)
{
var inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
var left = inputs[0];
var right = inputs[1];
board[left].Add(right);
board[right].Add(left);
}
void DFS(int start, int depth)
{
nodeCheck[start] = true;
nodeDepth[depth] = depth;
foreach (var nextNode in board[start])
{
if (nodeCheck[nextNode]) continue;
nodeParent[nextNode] = start;
DFS(nextNode, depth + 1);
}
}
int LCA(int A, int B)
{
while (nodeDepth[A] != nodeDepth[B])
{
if (nodeDepth[A] > nodeDepth[B]) A = nodeParent[A];
else B = nodeParent[B];
while (A != B)
{
A = nodeParent[A];
B = nodeParent[B];
}
}
return A;
}
C#
복사
메모리를 사용해 시간 감축
위의 LCA 코드를 메모리를 좀 더 사용해서, 시간을 단축 시킬 수 있습니다.
바로 노드에서 자신의 부모들을 저장하는 방법이죠.
즉, 위의 nodeParent를 2차원 배열로 작성함으로써 좀 더 빠르게 부모를 찾을 수 있습니다.
사용법
모든 노드에 대해 깊이를 찾고 저장합니다. (최상위 노드 부터, 차례대로 계산됩니다.)
1.
가장 가까운 공통 조상을 찾기 위한 두 노드를 설정합니다.
2.
모든 노드의 자신의 부모, 깊이를 찾고 저장합니다.
3.
위에서 찾은 부모 노드 들을 활용하여, 자신의 부모 조상들을 찾고 저장합니다.
4.
두 노드 중 더 높은 깊이의 노드를 더 낮은 노드의 깊이와 동일하도록 부모의 노드로 변경합니다.
ㄴ 여기서 부모 노드를 찾을 때, log 지수만큼 시간 복잡도를 발생 시키기 위해, 자신의 바로 위의 부모가 아닌, 최대한 가깝게 갈 수 있는 부모 노드로 이동합니다.
5.
두 노드의 깊이가 같아졌다면, 해당 노드의 부모가 같아질 때까지 두 노드를 부모로 계속해서 갱신합니다.
아래 코드는 메모리를 사용해 시간 감축이 적용된 코드입니다.
var nodeCount = int.Parse(sr.ReadLine());
var log = (int)(Math.Log(nodeCount) + 1);
var nodeParent = new int[nodeCount + 1, log];
var nodeDepth = new int[nodeCount + 1];
var nodeCheck = new bool[nodeCount + 1];
var board = new List<List<int>>();
for (var b = 0; b < nodeCount; b++)
{
board.Add(new List<int>());
}
for (var n = 0; n < nodeCount; n++)
{
var inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
var left = inputs[0];
var right = inputs[1];
board[left].Add(right);
board[right].Add(left);
}
void DFS(int start, int depth)
{
nodeCheck[start] = true;
nodeDepth[depth] = depth;
foreach (var nextNode in board[start])
{
if (nodeCheck[nextNode]) continue;
nodeParent[nextNode, 0] = start;
DFS(nextNode, depth + 1);
}
}
void SetParent()
{
for (var parentDepth = 1; parentDepth < log; parentDepth++)
{
for (var currentNode = 1; currentNode <= nodeCount; currentNode++)
{
nodeParent[currentNode, parentDepth] =
nodeParent[nodeParent[currentNode, parentDepth - 1], parentDepth - 1];
}
}
}
int LCA(int A, int B)
{
if (nodeDepth[A] > nodeDepth[B])
{
(A, B) = (B, A);
}
for (var depth = log; depth > 0; depth--)
{
if (nodeDepth[B] - nodeDepth[A] < 1 << depth) continue;
B = nodeParent[B, depth];
}
if (A == B) return A;
for (var depth = log; depth > 0; depth--)
{
if (nodeParent[A, depth] != nodeParent[B, depth])
{
A = nodeParent[A, depth];
B = nodeParent[B, depth];
}
}
return nodeParent[A, 0];
}
DFS(1, 0);
SetParent();
// LCA(A,B);
C#
복사
