[나만 몰랐던 알고리즘] 최소 공통 조상, LCA

트리 구조에서 조상은 현재 노드 위에 있는 노드들이다.

LCA(최소 공통 조상)은 말 그대로 공통 조상 중에서 가장 낮은(높이가 최소인) 조상을 말한다.

---

트리를 보면, 루트 노트 1은 깊이 0을 가지고, 9번 노드는 깊이 3을 가지는 것을 볼 수 있다.

여기서 10과 5의 공통 조상은 1, 3이 있고 최소 공통 조상은 3이다.

 

LCA를 구하는 방법은, 나이브하게 접근하면 매번 트리를 타고 올라가면서 확인하는 방법이 있다. 가장 확실하지만 시간이 아주 오래 걸릴 수도 있다. 트리가 꼭 균형이 맞는다는 보장이 없으므로 심한 경우에는 노드 갯수만큼의 비교와 count가 필요하다.

따라서 많은 문제에서 LCA는 다른 방법으로 구하게 된다. 

 

LCA에서 가장 핵심이 되는 것은 배열 하나의 추가이다. DP와 비슷하다고 생각할 수도 있겠다.

여기서는 Parents[] 배열로 생각한다. 이 배열은 다음과 같은 값을 저장하고 있다.

Parents[K][V] = V 노드의 2^K번째 조상 번호

이 배열을 통해 우리는 최소 공통 조상을 더 빠르게 찾을 수 있다.

 

LCA의 흐름을 보면

1. 각 노드의 깊이를 구한다. - DFS로 구현 가능하다.
2. Parents배열을 구한다 - 노드 깊이 구할때 Parents[0][V] (직계 조상) 채울 수 있고, 이후 Parents[K+1][V] = Parents[K][Parents[K][V]] 식으로 채워나갈 수 있다.
3. LCA 구할 두 노드를 입력 받고, 노드의 높이를 맞춰준다.
4. 맞춰진 높이에서 같은 높이씩 올려가며 LCA를 찾는다.

이런 흐름으로 볼 수 있다.

각 단계를 코드로 확인해보자.

각 노드의 깊이를 구한다.

void initTree(int cur_node, std::vector<int> adj[])
{
    for (int i = 0 ; i < adj[cur_node].size(); i++)
    {
        int next = adj[cur_node][i];
        if(depth[next] == -1) //다음 탐색할 노드가 값이 안들어가있는 경우 (자식인 경우)
        {
            depth[next] = depth[cur_node] + 1;
            parents[0][next] = cur_node;
            initTree(next, adj);
        }
    }
}

노드의 깊이를 구해서 depth[] 전역 배열에 넣어주는 DFS 코드이다. 현재 노드에서 연결되어있는 것들을 순회하면서 depth[] 값이 -1이면 자신의 자식으로 보고 depth 값을 채워준다. 

이후 parents[0][V]도 채워준다. parents[0][V] 값은 V 노드의 2^0 번째 조상 -> 직계조상이므로 부모자식 관계를 구하며 채우는 이 함수에서 쉽게 넣어줄 수 있다.

Parents[] 배열을 구한다.

for (int K = 0 ; K < MAX - 1; K++)
    {
        for (int V = 1 ; V < N; V++) // V[0]은 루트.
        {
            if (parents[K][V] != -1) //parents 배열의 해당 자리가 값이 있으면
                parents[K+1][V] = parents[K][parents[K][V]]; //위로 채워나가기;
        }
    }

Parents[0][v] 값은 위 단계에서 채웠고, 해당 채워진 값을 활용해 나머지 값을 채워나간다.

parents[K][V] 는 V 노드의 2^K 번째 조상이라고 했다. 따라서 parents[K + 1][V] 의 값은 V 노드의 2*2^K 번째 조상이므로,

V의 2^(K+1) 번째 조상은 V의 2^K 번째 조상(parents[K][V]) 의 2^K 번째 조상(parents[K][parents[K][V]]) 이다.

이 논리를 이용해 K를 늘려가며 N까지 순회하며 배열을 채운다.

LCA를 구할 두 노드의 높이를 입력받고, 높이를 맞춰준다.

int u, v;
std::cin >> u >> v;
u--;
v--;

if (depth[u] < depth[v])
    std::swap(u,v);
int diff = depth[u] - depth[v];

for (int bit = 0; diff; bit++) // 2진법으로 보고 올림. 
{
    if (diff % 2)
        u = parents[bit][u];
    diff /= 2;
}

두 노드의 인덱스를 받는다. (여기선 0부터 세므로 각 1을 빼준다.) 두 노드의 차이를 구하고 높이를 맞춰준다.

여기서 신기한 접근이 나온다. diff를 2진수로 보고 각 비트가 1일 때 parents를 올려준다.

예를 들어, 두 노드 depth의 차이가 11일 경우 11의 2진수는 1011이다. 따라서 2^0(bit == 0), 2^1(bit == 1), 2^3(bit ==3) 일때 u를 올려주게 된다.

그러면 아주 신박하게도 두 노드의 depth가 같게 된다.

맞춰진 높이에서 같은 높이씩 올려가며 LCA를 찾는다.

for (int height = MAX - 1; height >= 0; height--)
{
    //가장 위 높이서부터 비교 ... 루트는 당연히 공통조상이므로 if에 안걸리고 어느순간 조상이 달라질때 해당 노드로 갱신.
    if (parents[height][u] != -1 && parents[height][u] != parents[height][v])
    {
        u = parents[height][u];
        v = parents[height][v];                
    }
    //u, v 갱신하고 왜 height를 다시 높여서 연산하지 않는가?
    //갱신하고 난 뒤, height를 1 높인다 가정하면, 이미 갱신 전에 if에서 걸리지 않은 공통조상이었기 때문에, 그냥 탐색을 이어나가면 됨!
}
u = parents[0][u] ;

두 노드 높이가 같아졌으므로, 이제 양 노드를 같은 높이만큼 올려가며 LCA를 찾는다.

하지만 코드는 살짝 다르게 흐름이 흘러간다.

Parents 배열의 맨 위부터 훑고 내려오며 두 노드의 parents[height]가 달라질때를 찾는다. 루트부터 내려온다고 생각하면 무조건 공통 조상이므로 같다가 어느순간 공통 조상이 아닌 때가 온다. 이 때 u와 v를 그때의 값으로 바꿔준다. 이 후 똑같이 해당 노드에서 탐색을 계속 해나가며 조상이 갈라질때마다 u와 v를 갱신해준다.

for 루프가 다 돌아가면, u와 v는 LCA 바로 밑 노드를 각각 가르키고 있다.

u의 부모를 가르키도록 하고 u를 확인하면 드디어 LCA를 찾을 수 있다.

---

이렇게 LCA를 효율적으로 찾는 방법을 알아보았다.

생각보다 어려워서 힘들었는데, 한번 이해하고 나니 진짜 이거 생각한사람들 천재인것 같다.

depth를 2진수로 생각한다 라는 이해가 되고 나면 이제 이 문제를 해결하는데 조금 수월해지는 것 같다.