BOJ 11437 LCA ( Least / Lowest Common Ancestor )

LCA(Least/Lowest Common Ancestor, 최소/최저 공통 조상)를 공부해 보려고 한다.

LCA, 최소 공통 조상은 두 노드를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 말한다. 두 노드에서 조상을 찾아 올라가면서 발견되는 공통된 조상중 가장 먼저 발견되는 조상...

LCA를 구하는 방법은 O(n)방법과 O(logn)방법이 있는데,

1. O(n) 방법
 일단 각 노드까지의 depth와 각 노드의 parent를 dfs를 돌면서 구한다.
그리고 노드 u, v가 주어지면, u, v의 depth가 같게 맞춰야 한다. depth가 큰 노드가 작은 노드의 depth까지 부모를 타고 올라간다. 이제 두 노드의 depth가 같아졌으면 두 노드 모두 함께 하나씩 위로 올라가면서 두 노드가 같아질 때까지 올라간다. 같아지면 그것이 최소 공통 조상이 된다. 최소 공통 조상은 두 노드의 공통 조상중에 가장 먼저 발견되는 조상이므로 이렇게 구할 수 있는데 이 방법의 시간 복잡도는 트리의 모양에 따라 O(logn)이 될 수도 있지만, 최악의 경우 일렬로 쭉 펴진 트리(skewed tree)에서는 O(n)이 걸린다.

2. O(logn) 방법 - DP 이용
 위의 O(n)방법과 큰 틀은 같은데, 좀 더 빠르게 하는 방법이다.
원래는 parent배열에 자신의 바로 위 부모만 저장했다면, 이제 parent[node][k]배열에 node의 2의 k제곱 번째 조상(부모)을 저장한다.
2의 k제곱 = 2의 k-1제곱 + 2의 k-1제곱 이므로 node의 2의 k제곱번째 조상은 node의 2의 k-1제곱 번째 조상의 2의 k-1제곱번째 조상이 될 것이다. 즉,
 parent[node][k]=parent[ parent[node][k-1] ][k-1] 로 나타낼 수 있고, parent[node][k]는 parent[x][k-1]을 이용해서 구할 수 있으므로 dp로 parent배열을 n log n만에 구해놓을 수 있다.
이렇게 O(nlogn)에 전처리를 해놓고, 위에서 했던 과정을 좀 더 빠르게 해보겠다.

노드 u, v가 주어지면, 먼저 u, v의 depth가 같게 맞춰야 하는데, 두 노드의 depth차이를 구한다음에 그 depth차이를 이진수로 변환한다. 예를 들어 그 차이가 13이라고 하면 13은 이진수로 1101이므로 13 = 1101(2) = 2의 3제곱 + 2의 2제곱 + 2의 0제곱  이므로 O(logn)만에 두 노드의 depth를 맞출 수 있다.
이제 depth를 맞췄다면, 두 노드가 같이 올라가면서 최소 공통 조상을 찾아야 하는데, 이 과정도 하나씩 올라가지 않고 좀 더 빠르게 할 수 있다. 일단 u, v의 최소 공통 조상 위의 조상들은 모두 같을 수 밖에 없다. 그리고 우리가 찾아야 하는 것은 그 중 최소 공통 조상인데, 문제는 최소 공통 조상이 u와 v에서 정확히 2의 k제곱 만큼 떨어져 있지 않을 수가 있다. 그렇기 때문에 먼저 가장 큰 k부터 시작해서 k를 줄여나가면서 parent[u][k]와 parent[v][k]가 서로 다르면서 (즉 서로 조상이 다른) 가장 k가 큰 경우를 찾고 그 경우에 u, v를 2의 k제곱 만큼 올려준다. 

여기서 쓰이는 원리는 parent[u][k]와 parent[v][k]가 서로 다른데, parent[u][k+1]과 parent[v][k+1]이 서로 같다면 parent[u][k]와 parent[u][k+1]사이에 최소 공통 조상이 있다는 원리이다. 그래서 일단 parent[u][k] != parent[v][k]이면서 k가 최대인 경우를 찾아야 한다. 그리고 k+1까지 올라가면서 parent[u][k] == parent[v][k]가 되는 최소 공통 조상을 찾는 것이다.

여기서 의문이 생기는 것이, 예를 들어 2의 3제곱 과 2의 4제곱 위 조상들 사이에 최소 공통 조상이 있다면 그 사이를 다 볼 수 있을까?
다 볼 수 있다. 일단 2의 3제곱에서 다르기 때문에 멈추고(k는 3) k는 계속 줄어들면서 k=2일 때 parent[u][2] != parent[v][2]이면 u와 v를 2의 2제곱씩 올려주고, 
만약 parent[u][2]==parent[v][2] 라면 k=1이 되어 또 확인하는 작업을 하고.. 이러다보면
8에서 16사이의 모든 수를 조건에 따라 다 갈 수 있게 된다. 예를 들어 15까지 가는 과정을 보면 8-> 8+4=12 -> 8+4+2=14 -> 8+4+2+1 =>15 => 16번째 위의 조상이 LCA가 된다.
하나 더 9까지 가는 과정을 보면
8 -> 8+1=9 => 10번째 위의 조상이 LCA가 된다.
==> 사실 생각해보면 어떤 수든 간에 2의 x제곱의 합으로 나타낼 수 있다. 바로 2진법을 생각해보면 쉽다. 어떤 수든 이진법으로 나타내고 보면 위의 방식이 쉽게 이해가 될 것이다.

이렇게 k는 가장 큰 수 부터 시작해서 1씩 줄여가면서 parent[u][k] != parent[v][k]일 때마다 계속 u, v를 2의 k제곱씩 올리고, parent[u][k]==parent[v][k]이면 올리지 않고 하다보면 결국에 u, v가 u != v인 최대값까지 가게 될 것이고 최종적으로 구하는 최소 공통 조상은 u, v의 부모가 된다. 뭐랄까... 약간 이분탐색 느낌이랑 비슷하다. 
어쨌든 이 방법으로 O(logn)만에 조상을 찾을 수 있다. 

직접 구현해 보고 있는데, 내 실력이 부족해서인지 구현이 쉽지는 않다. 예를 들어 depth를 맞추는 과정에서 이진수로 변환한다든지.. 하는 부분이 아직 나에겐 까다롭다. 연습을 열심히 해야겠다.

계속 에러가 나고 문제가 좀 많았다. 주의해야할 점을 적어보겠다.
 parent[node][k] = parent[parent[node][k-1]][k-1]에서 parent[node][k-1]이 값이 -1이 아닌 경우에만 이 대입연산을 해줘야 한다. 그리고 node는 (노드가 1번부터 있다면) 2번 부터 for문을 돌려줘야하고... k는 1부터 해줘야 한다(k가 0인 경우는 dfs로 구했음)
 그리고 만약 u와 v중에서 u가 v의 조상이라든가, v가 u의 조상인 경우는 두 노드중 조상인 노드가 최소 공통 조상이 되기 때문에, 두 노드의 깊이를 같게 맞춰줬는데 두 노드가 같다면 바로 최소 공통 조상을 return하면 된다. 2의 k제곱씩 같이 올라가는 것을 하면 안된다.


3. O(logn) 방법 - Segment Tree(RMQ) 이용
 Segment tree를 사용하기 위해서 트리의 정점들을 일렬로 나열해야 하는데, 트리를 preorder로 순회하면서 방문하는 정점들을 나열한다. 그런데 preorder로 순회하면서 이미 방문했더라도 자식을 방문하고 다시 부모로 돌아오면서 방문하는 정점(부모들)도 나열해준다.
이렇게 나열한 수열에서 어떤 두 정점을 골랐을 때, 그 두 정점 사이에 있는 수들 중 depth가 가장 낮은 것(이 중 최상위 노드)이 최소 공통 조상이 된다.

preorder로 방문하면서 돌아오면서 다시 방문하는 점들까지 기록해서 놓으면, u에서 v사이으 정점들은 모두 u를 방문하고 v를 방문하기 까지의 중간에 거친 정점들이라 볼 수 있는데, u와 v의 최소 공통 조상이 있다면 u와 v는 최소 공통 조상에서 갈라지는 서로 다른 서브트리에 포함되어 있을 것이다.(물론 u, v중 하나가 최소 공통 조상인 경우는 예외) 그렇기 때문에, u를 방문하고 v를 방문하려면 최소 공통 조상을 지날 수 밖에 없고, 그 최소공통 조상보다 더 상위 노드를 방문하려면, 최소 공통 조상의 자손들을 다 방문한 후에나 가능하기 때문에, u를 방문하고 v를 방문하러 가는 도중에는 최소 공통 조상이 방문하는 최상위 노드가 될 것이다.

자 이제 u, v가 있으면 u와 v사이의 점들 중에서 depth가 제일 작은 점을 고르면 되는데, 이 것을 RMQ(segment tree)로 하면 O(logn)만에 가능하다. depth를 비교하지 않고도 할 수 있는 방법이 있다. 바로 preorder로 순회하면서 각 정점에 순번을 매기면 항상 부모부터 먼저 방문하기 때문에 부모 노드의 순번이 자식노드의 순번보다 작을 수 밖에 없다. 즉 최소 공통 조상은 u, v사이의 구간에서 가장 작은 순번을 가진 정점이 되는 것이다.

이게 구현을 하려고 하면 쉽지 않은데, 구현 방법은 JM book에 코드와 같이 자세히 나와있다.

- JM book(알고리즘 문제 해결 전략- 구종만 저)을 읽고 정리해 봤는데, JM book 설명이 훨씬 낫다. JM book을 꼭 읽어볼 것.


참조 : 알고리즘 문제 해결 전략 - 구종만 저,  kks227님 블로그,  https://www.acmicpc.net/board/view/332