최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상?

사실 처음 LCA문제를 접했을 때는, 별로 활용될 구석이 없을 것 같아서
이 문제에만 특별히 쓰이는거구나~ 하고 적당히 베끼는 것에 가까울 정도로 해결하고 넘어갔다.

백준 1922번 : 네트워크 연결 그런데, 이 문제를 보고 나서 LCA가 굉장히 가치있는 알고리즘이라고 생각하게 됐다.

LCA란, 트리 내에서 두 정점을 선택했을 때, 서로의 부모노드를 타고 올라가다가
처음 만나는 지점을 찾아내는 알고리즘을 말한다.

예를 들어, 위와 같은 트리가 있을 때, 12과 15의 lca는 2가 된다.
서로의 부모를 타고 올라갔을 때, 가장 먼저 공통부모를 갖는 곳이 2이기 때문이다.

물론 이런 작은 경우에는 한쪽을 먼저 타고 올라가며 visited배열을 변경하고,
나머지 한쪽을 타고 올라가며 겹치는 부분을 찾는 방법도 있을 수 있지만,
만나본 대부분의 문제의 경우 정점의 수를 100000개까지로 주며 테스트케이스 횟수 또한 많기때문에
시간이 매우 부족할 수 밖에 없다.

알고리즘 구현

depth 결정

일단 가장 먼저 각 노드들의 depth를 결정해주어야 한다.

말 그대로 1번노드의 depth를 1로 두었을 때, 다른 노드들의 깊이를 저장하는 것이다.
이는 추후에 lca를 얻고자 하는 두 노드의 깊이를 맞춰주는데 활용한다.

void dfs(int n, int dep)
{

    depth[n] = dep;
    for (int i = 0; i < (int)tree[n].size(); i++)
    {
        if (!visited[tree[n][i]])
        {
            visited[tree[n][i]] = true;
            dfs(tree[n][i], dep + 1);
            dp[tree[n][i]][0] = n;
        }
    }
}

해당함수는 각 노드들의 depth를 결정함과 함께, dp배열을 채워나간다.

visited배열을 사용하는 이유는, 기본적으로 입력값이 양방향으로 주어지기 때문에
1번노드를 기준으로 뿌리내려가며 depth를 결정해주기 위함이다.
(예를 들어, 위 그림에서는 현재 tree[1]에 2가 들어가있고 tree[2]에도 1이 들어가있다.)

dp[n][m]배열은 각노드들을 기준으로 2의 m승에 있는 노드들의 정보를 담고 있다. 요컨데 dp[7][0]은 7번노드의 2의 0승에 있는 노드를 가리키므로 dp[7][0] = 4이다.

여기서는 dp[tree[n][i]][0] = n으로 자신의 부모노드만을 먼저 지정해준다.

dp결정

    for (int j = 1; j < 21; j++)
        for (int i = 1; i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];

다음은 dp값을 모두 결정해주어야 한다.

dp[i][j] = dp[dp[i][j - 1]][j - 1]이라는 식이 처음에는 굉장히 헷갈렸다.

그대로 풀이하면 i의 2^j번째 부모를 가리키는 dp에
i의 2^(j - 1)번째 부모의 j - 1번째 부모노드를 저장한다.
사실 이렇게 써놓아도 단번에 이해하긴 힘들었다.

다시 그림을 예로 들면,
dp[15][2]는 15의 2^2번째 부모 정보를 저장한다.
이를 결정하기위해서 dp[dp[15][2 - 1]][2 - 1]의 값을 가져온다.
dp[15][1] 의 경우는 14의 2^1번째 부모인 7을 가리키고
dp[7][1] 은 7의 2^1번째 부모인 2를 가리키므로
결과적으로 dp[15][2]는 2라는 값을 갖게 된다.

이 때, dp[15][1]과 dp[7][1]은 for문에 의해 이미 결정되어 있다.

위와 같은 방식으로 j의 값이 16정도만 되어도 10만번 위의 노드정도까지도 충분히 저장할 수 있다.

lca구하기

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);

    for (int i = 20; i >= 0; i--)
        if (depth[a] - depth[b] >= (1 << i))
            a = dp[a][i];

    if (a == b) return a;

    for (int i = 20; i >= 0; i--)
    {
        if (dp[a][i] != dp[b][i])
        {
            a = dp[a][i];
            b = dp[b][i];
        }
    }

    return dp[a][0];
}

lca를 구하는 함수는 위와 같이 구성되어 있다.

일단 첫번째로, a와 b중에 depth가 더 깊은 쪽을 a로 둔다.
그리고 두 값의 depth를 같게 맞춰주는 과정으로 넘어간다.

i가 큰 수부터 0까지 for문을 두고 depth[a] - depth[b] >= (1 << i)인지 검사한다.
즉, 현재 지정된 두 노드의 depth차이가 2^i보다 큰지 검사한다.

i값이 작아짐에 따라 두 노드의 depth차이가 2^i보다 크다면 a의 값을 dp[a][i]로 바꿔준다.
이 과정이 의미하는 바는, a의 값을 b보다 작거나 같은 범위 내에서
가장 큰 2^i만큼을 증가시켜 a와 b가 가까워지도록 하는 것이다.

i의 범위는 0까지였으므로 결국 1 << i는 모든 2^i를 나타내고,
이 수들의 합으로 원하는 모든 자연수를 나타낼 수 있으므로 위 과정을 반복하면 depth[a]와 depth[b]를 같게 만들 수 있다.

다음으로 a와 b가 같은지 검사한다.

만약 a와 b가 같다면 이미 공통조상에 도달한 것이므로 더이상 검사할 필요가 없기 때문에
바로 a를 리턴해준다.

그렇지 않다면, 다시 i를 0까지 감소하도록 두고 dp[a][i]와 dp[b][i]가 같은지 검사한다. 즉, a의 2^i번째 부모와 b의 2^i번째 부모가 같은지 검사한다.

만약 같을경우, 이것이 ‘최소’공통 조상인지 알 수 없으므로 다음 i로 넘어간다.
같지 않을경우, 최소 공통 조상보다 작은 값이므로 a와 b를 그 각각 서로 2^i번째 부모로 갱신한다.

서로 2^i번째 부모가 같은 경우는 모두 패스했으므로,
결과적으로 a와 b는 서로 부모를 타고 올라가 최소공통조상의 직전에 각각 멈춘다.
그렇기에 최종적으로 리턴해주는 값은 a 또는 b가 아닌 dp[a][0] 또는 dp[b][0]이 된다.

예시

위의 그림 예시로 전체 과정을 살펴보자.

a는 12이고 b는 15라 할 때, 둘의 lca값을 찾아보자.

depth[a]는 5이고 depth[b]는 6이므로 서로의 값을 바꿔주어 a는 15, b는 12이 된다.

이제 서로의 depth값을 맞춰주어야 한다. depth[a] - depth[b]는 1이므로 i의 값이 0일 때 비로소 1 << i보다 작거나 같아진다.
그러므로 a는 dp[a][0] 즉 a = dp[a][0] = (a의 2^0번째 부모) = 11가 된다.

i = 0을 마지막으로 for문이 종료되면, a와 b가 같은지 검사한다.
현재 a는 11, b는 12이므로 다음으로 넘어간다.

i가 0까지 작아짐에 따라 공통조상이 아닌 i값을 검사한다.

i가 20~3일 때에는 dp[a][i] = dp[b][i] = 0이므로 아무일도 일어나지 않는다.

i가 2일 때에는 dp[a][i] = dp[b][i] = 1이므로 역시 아무일도 일어나지 않는다.

i가 1일 때 dp[a][i] = dp[11][1] = 4이고 dp[b][i] = dp[12][1] = 5이므로
a = dp[11][1] = 4, b = dp[12][1] = 5로 갱신된다.

마지막으로 i가 0일 때, dp[a][i] = dp[b][i] = 1이므로 아무일도 일어나지 않는다.

위의 과정으로 a와 b는 각각 최소공통조상의 바로 아래까지 도달했으므로
최종적으로 dp[a][0] = dp[4][0] = 2라는 값을 리턴받게 된다.

문제에서의 활용

위 과정을 그대로 보여주는 문제들이거나, 몇몇 문제들은 위 과정을 변형하기보다
과정내에 다른 배열을 섞어넣어 원하는 값을 얻어내는 방식으로 답을 구할 수 있었다.

처음엔 굉장히 어렵게 느꼈는데 반복해서 서너번 활용하다 보니 굉장히 효율적이고
신기한 알고리즘이라고 생각하게 되었다.