알고리즘 - LCA (최소 공통 조상 탐색)

LCA(Lowest Common Ancestor) 알고리즘에 대해 알아보자.

 

먼저 LCA란 뭘까? 

LCA는 한글로 최소 공통 조상을 의미한다.

 

 

위와 같은 트리가 있다고 치자.

 

노란색으로 칠해진 9번 노드와 8번 노드의 최소 공통 조상 노드를 찾고자 한다.

조상 노드란, 부모노드, 부모의 부모노드 등등 상위에 있는 모든 노드를 의미한다.

 

9번 노드의 경우 7번노드, 3번노드, 1번 노드가 조상노드가 될 것이다.

8번 노드의 경우 3번노드, 1번노드가 조상 노드가 될 것이다.

 

보면, 9번 노드와 8번 노드의 조상노드중 겹치는 노드가 있다.

3번 노드와 1번 노드이다. 이 두 노드중 더 가깝게 위치한 노드는 3번 노드이다.

 

이처럼 공통된 조상 중에서 가장 가까이 있는 노드 (3번 노드)를 최소 공통 조상 노드(LCA)라고 한다.

 

그런데, LCA에선 하나 유의해야 할 점이 있다.

바로 조상노드가 본인을 포함한다는 점이다.

 

위에서는

 

9번 노드의 조상노드 : 7, 3, 1

8번 노드의 조상노드 : 3, 1

 

이라고 설명했지만 실제로는 

 

9번 노드의 조상노드 : 9, 7, 3, 1

8번 노드의 조상노드 : 8, 3, 1

인 것이다.

 

왜 조상노드인데 본인을 포함하냐라고 생각하겠지만 아래 그림을 보자.

여기서, 1번 노드와 3번 노드의 공통 조상 노드를 찾겠다고 해보자.

 

1번 노드의 경우엔 조상노드가 없다.

반면, 3번노드의 경우 1번노드와 2번노드가 조상노드이다.

 

1번 노드는 누군가의 조상노드이면서 본인은 조상노드를 가지고 있지 않다.

 

이러한 경우 "1과 3의 최소 공통 조상 노드는 없다" 라고 할 것인가?

아니다. 그냥 1을 최소 공통 조상 노드로 설정하면 된다.

 

이 알고리즘은 진짜 조상노드를 찾기 위한 알고리즘이 아니라, 어느 노드부터 공통되어 있는가를 찾기 위한 알고리즘이다.

 

이름이 최소 공통 조상 노드이다 보니, 자기 자신을 포함하는 이유에 대해 헷갈리는 부분이 많았다.

허나 이름의 편견에서 벗어나서 알고리즘의 목적을 생각하면 본인노드를 포함하는 것이 더 적합하다고 본다.

 

그런 이유로 3와 2의 최소 공통 조상 노드 역시 1이 아닌 2가 된다.

 

최소 공통 조상 노드에 대해서 알아보았으니 이제 구하는 법을 알아보자.

 

 

여기서 6과 9의 최소 공통 조상 노드를 찾아보자.

 

먼저, 두 노드의 공통 조상 노드를 찾기 위해선 깊이를 맞춰주어야 한다.

깊이란, 루트노드를 기준으로 얼만큼 내려가 있느냐를 의미한다.

 

 

위 그림처럼 루트노드와의 거리를 깊이라고 한다.

 

그렇다면, 이 깊이를 왜 맞춰주어야 할까?

동일한 깊이에서부터 동일하게 한 칸씩 위로 올라가보며 탐색할 것이기 때문이다.

 

아래에 설명을 쭉 보면 이해 될 것이다.

먼저 깊이를 맞춰 주겠다.

 

 

이처럼 9번노드가 아닌 7번 노드를 선택함으로써 두 노드의 깊이가 같아졌다.

이제 한 칸씩 올라가며 부모노드를 비교해보자.

 

 

이렇게 한 칸 올라가 보았다.

4번 노드와 5번 노드는 서로 다르다.

두 노드가 같아질 때까지 계속 올라가보자.

 

 

한칸 올라갔더니, 두 노드가 같은 곳에서 만나게 되었다. 

즉, 현재 노드가 두 노드의 최소 공통 조상 노드가 되는 것이다.

 

이런식으로 선형으로 최소공통조상 노드를 탐색하는 방법이 가장 간단한 방법이다.

하지만 문제가 하나 있다.

 

이런 식으로 5만개의 노드가 한줄로 연결되어있다고 치자.

그렇다면 연산을 최대 5만번까지 해야한다.

1억개라면? 1억번을 해야한다.

O(n)의 시간복잡도를 가지는 만큼 n이 늘어날수록 연산량이 많아지고 부담스러워진다.

 

시간복잡도를 줄이기 위해 2의 지수를 이용하여 탐색하는 방법을 주로 사용하게 된다.

전체적인 과정은 위의 선형탐색과 동일하다.

하지만, 1씩 위로 움직이며 깊이를 맞추고 조상을 탐색하는 것이 아니라 2의 승수만큼 움직이며 깊이를 맞추고 조상을 탐색한다.

 

 

 

아래 그림을 보자.

 

50000과 2의 최소 공통 조상을 찾기 위해서 위에서 설명한 것처럼 선형으로 탐색하게 되면 49999번의 연산이 필요하다.

2의 지수를 사용하면 어떻게 될까?

 

먼저 노드가 최대 5만개이기 때문에 최대 지수를 구해보겠다.

2^15 < 50000 < 2^16 이다. 16 이상의 지수는 의미가 없기 때문에 최대 지수를 15로 설정해보겠다.

편의를 위해 최대 지수를 MaxE 라고 하겠다.

 

노드의 번호가 순서대로 정렬되어있다고 가정을 먼저 하겠다.

50000에서 위로 2^(MaxE) 만큼 이동해보자.

50000 - 32768 = 17232가 된다.

 

현재 깊이가 17232이므로, 노드 2보다 여전히 깊이가 깊다.

 

이번엔 2^(MaxE - 1)만큼 더 이동해보겠다.

17232 - 16384 = 848이 된다.

 

현재 깊이가 848이므로, 노드 2보다 여전히 깊이가 깊다.

 

이번엔 2^(MaxE - 2)만큼 더 이동해보겠다.

848 - 8192 = -7344 이다. 깊이는 최소 0이기 때문에 음수 깊이가 나왔다는 뜻은 이동할 수 없다는 뜻이다.

이럴 땐 이동하지 않도록 하겠다.

 

다음은 2^(MaxE - 3)을 이동해보고, 2^(MaxE - 4)를 이동해보고.......

 

2^(MaxE - i) 만큼 계속 이동하다 보면 깊이가 노드 2와 같아지는 시점이 온다.

(모든 정수는 2의 지수의 합으로 표현이 가능하기 때문에 이론적으로 반드시 같아지는 시점이 나온다.)

 

반복문은 최대 MaxE + 1 번만큼 돌기 때문에, 아무리 많아도 16번까지밖에 돌지 않는다.

선형으로 탐색할 땐 49999번을 돌아야 했던 반복문이 16번으로 줄어들었다.

 

O(N)의 시간복잡도가O(LogN)이 된 것이다.

 

깊이를 맞추고 조상을 탐색할 때에도 이처럼 2의 지수를 이용해서 이동하며 탐색하기 때문에

시간복잡도가 엄청나게 줄어들게 된다.

 

 

그렇다면 이걸 어떻게 구현해야 할까?

---

 

먼저 위와 같이 최대 깊이가 4인 트리라고 가정해보자.

배열을 두 만들어 보겠다.

 

 

이렇게 만들어보자. 가로는 노드의 번호이다. 총 노드가 9개 이므로 가로는 9의 길이로 만들어 주었다.

세로는 2^i번째 조상 노드의 번호이다.

 

위에서 말했지만 조상으로 이동하며 탐색할 때, 2^i만큼 이동하며 탐색할 것이다. 그렇기 때문에 2^i번째 조상이 누구인가를 알고 있어야 한다.

 

다음은 깊이를 저장하는 노드이다.

깊이를 맞춘 뒤에 조상노드를 탐색하기 때문에 깊이에 대한 정보도 알아야 한다.

 

 

1번 노드부터 먼저 배열을 채워보자.

반복문을 돌며 해야 할 것은 현재 노드의 깊이를 기록하는 것과 조상노드를 기록하는 것이다.

 

현재 노드의 깊이는 이렇게 표현할 수 있다.

현재 노드의 깊이 =  부모 노드의 깊이 + 1

 

부모노드와 무조건 깊이가 1만큼 차이나기 때문에 이와 같이 표현할 수 있다.

 

다음은 조상 노드를 기록할 것이다.먼저, DP를 이용하는 이유는 조상 노드에 기록된 조상 노드들을 그대로 가져오기 위해서 이다.

 

이 트리에서 보면, 6의 조상노드는  6, 4, 2, 1이다.

4의 조상노드는 4, 2, 1이다.

2의 조상노드는 2, 1이다.

 

즉, 조상의 조상 노드는 동시에 나의 조상노드인 것이다.

 

그렇다면 조상노드를 모두 기록할 것인가?

아니다. 우리는 2의 지수를 이용하기로 했기 때문에 2^i번째 조상 노드만 기록할 것이다.

 

예제를 하나 보자.

 

8번 노드에서 1번 노드로 가기 위해선 4칸을 올라가야 한다.

즉 2^2승만큼 이동해야 하는 것이다.

 

그런데, 이 것은 이렇게 표현할 수도 있다.

8에서 2^1승만큼 이동하여 5를 간 뒤, 5에서 2^1승만큼 이동하여 1로 가는 것이다.

 

즉, 8에서 2^i만큼 위로 올라간 노드는 8의 2^(i - 1) 번째 조상 노드의 2^(i - 1)번째 조상 노드인 것이다.

 

그렇기 때문에,

현재 노드의 2^i번째 조상 노드 =  2^(i - 1)번째 조상 노드의 2^(i - 1)번째 조상 노드

라는 점화식을 세울 수 있는 것이다.

 

이 점화식을 이용해, 2^1번째부터 2^MaxE 번째 조상노드까지 기록할 수 있는 것이다.

(만약, 2^i번째 조상노드가 없다면 그냥 0으로 저장하면 된다.)

 

 

먼저, 1번 노드의 경우 루트노드이므로 깊이가 0이다.

조상 노드또한 없으므로 모두 0으로 기록한다.

 

이제, DFS를 이용하여 1번과 연결된 노드를 탐색하자.

 

 

1번에는 2번과 3번 노드가 연결되어 있다.

2번 노드를 먼저 탐색해보자.

 

깊이는 부모노드의 깊이 + 1이므로 1이 된다.

 

2^0번째 조상 노드가 1번 노드이므로 1을 기록하고 나머지엔 0을 기록한다.

DFS 방식으로 탐색하고 있기 때문에, 다음엔 4번 노드로 이동해 보겠다.

 

깊이는 부모 노드의 깊이 + 1이므로 2가 된다.

 

 

2^0번째 조상은 2번 노드를 기록하고, 2^1번째 조상은 1번 노드를 기록해주자.

 

이와 같은 방식을 쭉 반복하여 모든 배열을 채우고 나면

 

이렇게 된다.

이제 그냥 조상을 타고다니며 탐색하면 끝이다.

위에서 설명했던 것처럼, 2^(MaxE - i)씩 이동하며 탐색하면 된다.

 

사실, 아이디어를 알아도 코드로 구현하는 건 상당히 쉽지 않은 일이다

아래의 링크에 해당 알고리즘을 사용하여 해결할 수 있는 기초 문제에 대한 풀이가 있다.

이 알고리즘을 어떻게 코드로 작성하는 지는 해당 문제 풀이를 보며 이해하는 것이 도움이 될 듯 하다.

 

백준 11437 - LCA, LCA2 (C++) (tistory.com)