LCA(Lowest Common Ancestor)

서론

우리는 종종 트리에서 u점과 v점의 거리 차이를 구하는 문제를 접하게 된다. 문제가 하나라면 순회하면서 찾아내면 되지만, 만약 쿼리로 주어진다면...? naive하게 짜다간 뚝배기가 깨진다.

따라서, 우리는 naive가 아니라 다른 방법을 찾아내야한다. 이 때, 우리는 하나의 중요한 점을 관찰할 수 있다. 바로, u와 v의 거리는 u와 v가 동시에 가르키는 공통 조상(Common Ancestor)과 관련이 있음을 알 수 있다. 그러면, 우리는 각 점에서 트리의 시작노드에서 그 노드까지의 거리를 저장해놓고, 공통조상까지의 거리를 구해서 빼면 됨을 알 수 있다. 그러면, 공통 조상은 어떻게 구할까? 이걸 지금 알아보도록 하자.

필요한 사전지식

구간 트리(흔히 Segement tree,세그먼트 트리라고 불림), Sparse table(중간에 트리의 내용이 바뀌지 않는다면 Init O(NlogN), Query O(1)에 처리), 트리에 관한 기본지식,DFS

추후 모든 내용 다 포스팅 예정

본론

우리가 알아볼 내용은 일반적인 트리에서의 Lowest Common Ancestor(이하 LCA)이다. LCA를 알아보는 이유는 보통 u점에서 v점까지 갈 때 걸리는 최소 거리를 물어보기 때문이다. 

LCA는 크게보면 3단계로 이루어진다.

단계

1. 각 노드를 방문. 방문 시에 새로 번호를 매긴다. 이유는 추후 설명

2. 새로 번호를 매긴 노드들을 dfs로 방문하여서 각 노드의 깊이를 기준으로 배열을 펼친다. 모든 Edge를 두번 방문하므로 배열의 총 길이는 2*N-2이 된다. 공간복잡도는 이 된다. 모든 간선을 두번씩 방문하므로 의 시간이 소모된다. 

3. 펼친거에서 RMQ를 적용시킨다. ( RMQ : Range Min Query의 줄임말로, 세그먼트 트리나 Sparse table을 활용하여 구간 내의 최소값을 구하는 과정이다)

각 단계별 설명을 자세히 해보도록 하겠다. 펜을 들고 아무 트리나 그린다음에, 차례대로 해보길 바란다.

First + Second

트리의 최대 높이에서부터 차례대로 dfs를 돌려서, 배열 3개를 만들어 낸다.

Serial : 방문한 차례대로 정점들을 기록해놓는 배열

Fi : Serial에서 정점 i가 처음 나타나는 인덱스를 기록해놓는 배열

Dep : 방문한 차례대로 정점 i가 나타내는 깊이를 기록해놓는 배열

다음 3개를 기록해내는 dfs 코드는 다음과 같다.

void dfs(int cur,int depth)
{
    Serial[idx]=cur;
    Fi[cur]=idx;
    Dep[idx++]=depth;
    for(int i=0;i<child[cur].size();i++)
    {
        dfs(child[cur][i],depth+1);
        Serial[idx]=cur;
        Dep[idx++]=depth;
    }
}

이렇게 하면, 성공적으로 Serial과 Fi, Dep배열의 갱신에 성공하였다!

Third

이제 두 정점 u,v의 LCA를 구하는 문제는 다른 문제로 변한다.(u>v) 바로 Serial[RMQ(Fi[u],Fi[v])]이다. 여기서 구하는 RMQ는 Dep 배열에 대한 RMQ이다. 세그먼트가 최소값을 띄는 인덱스를 반환한다하면 Serial을 씌워줘야 할 것이고, 값을 반환해준다면 Serial을 씌울 필요가 없다. 

Fi[u]와 Fi[v] 숫자들 사이에 존재하는 가장 작은 깊이를 찾고, 이가 몇번째로 방문했는지 알 수 있으므로 Serial에 넣으면 몇번째 정점이 나온다.

Time Complexity

시간복잡도를 분석하자. 

세그먼트 트리를 만드는데 O(N)이 소요되고, 만약 거리를 구하는 쿼리라면 일반적인 세그트리에서 값을 추적하는 거랑 동일하므로 O(logN)의 시간이 소요된다. 쿼리를 Q개라고 하면, 총 소모하는 시간복잡도는 O(N+QlogN)이다.

결론

일단 LCA에 대한 개념복습 겸 익힐 겸 문제를 조금 더 풀고, IOI 2014 Game 풀어봐야겠다  

수정(05-29,22:37)

LCA를 구할때 세그먼트 트리를 쓰는건 매우 어렵게 둘러가는것이라고 한다...

바뀌지 않을때에는 Sprase Table이나 그냥 dfs돌리면 된다.

제대로 공부하고 dfs와 Sprase Table에 대해 포스팅해야겠다