[BOJ 3584]

문제 바로가기 : https://www.acmicpc.net/problem/3584
이 풀이는 BOJ 11438 : LCA 2에서도 쓸 수 있습니다.
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

LCA(lowest common ancestor)

LCA 알고리즘에 관해서는 이곳에서 많은 도움을 받았습니다. 감사합니다.
자세하게 설명돼있으니 참고하시길 권합니다.

직역하면 최소 공통 조상. 두 노드를 찍고 조상으로 거슬러 올라갈 때 가장 빨리 만나는 노드를 찾는 알고리즘이다.
DP도 DP지만 특정 노드에서 2^k번째에 있는 부모로 바로 이동할 수 있다는 장점을 지녔다. 시간복잡도가 크게 감소한다.
핵심이 되는 점화식은 parent[u][k+1] = parent[parent[u][k]][k] 이다.
u의 2^(k+1)번째에 있는 부모는 parent[u][k]의 2^k번째에 있는 부모를 뜻한다.
조금 놀랍기도 하고 바로 와닿지 않을 수 있는 부분이라고 생각한다. 위 링크에서 자세하게 설명 돼있다!

review

input을 통해 이웃 노드를 추가시켜준 후 makeTree()에 속한 dfs()에서 각 노드당 1번째 부모를 갱신한다.
그리고 각 노드의 depth도 갱신해주자. 이 depth는 나중에 LCA를 찾는데 중요한 역할을 한다.
dfs()가 끝나면 1번째 뿐만 아니라 2^k번째(1, 2, 4…) 부모도 갱신해준다.

//바로 위에 있는 부모와 연결
void dfs(int cur, int d) {
    chk[cur] = true;
    depth[cur] = d; //깊이
    for (auto& next : node[cur]) {
        if (chk[next]) continue;
        parent[next][0] = cur; //next의 1(2^0)번째 부모는 cur
        dfs(next, d + 1);
    }
}

void makeTree() {
    dfs(root, 0);

    //노드 u(1~n)의 부모를 연결하기
    for (int k = 1; k < COL; k++) {
        for (int u = 1; u <= n; u++) {
            parent[u][k] = parent[parent[u][k - 1]][k - 1];
        }
    }
}

2^k번만 갱신해주면 3, 5, 6..번째 부모는 어떻게 접근하는걸까 싶었는데 생각보다 간단했다.
u에서 3번째 부모를 찾기위해 먼저 parent[u][1]로 이동하자. u의 2(2^1)번째 부모이고 이를 v라 하자.
그리고 v의 1번째 부모로 이동하면 되므로 u의 3번째 부모는 parent[v][0]가 된다.

또 다른 예를 들자면 모든 10진수는 2진법으로 나타낼 수 있다.
10진수에서 가장 큰 10의 자릿수를 맨 앞에 놓는 것처럼 2도 마찬가지다.
그렇게 앞에서부터 뒤로 쭉 채워나가면 2진법이 완성된다. 위의 3은 2진법으로 나타내면 11이다.
처음에 2^1로 이동했고, 그 다음에 2^0번 이동했으니 2진법으로 나타내면 (2^1) * 1 + (2^0) * 1 = 11이 되겠다.

모든 10진수를 2진법으로 나타낼 수 있다는건 2^k번째 부모의 정보만 갖고 있어도 어느 부모에나 접근할 수 있다는걸 말한다!
처음 볼 때 계속 2^k가 등장해서 생소해가지고 이해하기 어려웠는데.. 잘 이해됐음 좋겠다.

여기까지 트리를 완성했다. 그럼 이 트리에서 LCA를 찾아주면 된다.
두 노드(a, b)의 depth가 같을 때 depth를 계속 올려준다. 이 때 a, b의 부모가 같으면 답이다.
근데 a, b의 depth가 같다는 보장이 없다. 때문에 a, b의 depth를 같을 때까지 위치를 수정해줘야 한다.
b가 있는 경로(parent[b][])에서 depth[a]와 같은 depth에 있는 위치까지 달려가면 된다!
(여기서 a, b중 깊은 쪽에 있는건 b로 설정이 된 상태이다)

//깊이가 다른 만큼 맞춰주기
//b의 2^i번째 조상이 a의 깊이보다 크거나 같으면 업데이트
for (int i = COL-1; i >= 0; i--) {
    if (depth[a] <= depth[parent[b][i]])
        b = parent[b][i];
}

이렇게 달려갔는데 만약 b의 경로에서 a가 있었다면 depth가 같으므로 a==b가 된다.
그럼 공통 조상은 a or b가 되므로 바로 리턴해준다.

//a와 b가 같다면 -> 최소 공통 조상
if (a == b) return a;

이제 다른 경로에 있다면 원래 계획대로 같은 조상을 만날 때까지 같이 움직이면 된다.
노드 밖의 범위 밖의 parent[][]는 모두 0으로 초기화 돼있어서 if절에서 false가 된다. (0 != 0)
그럼 최종적으로 a, b는 LCA 바로 아래의 자식으로 이동하게 된다. 그럼 1번째 부모를 반환하자.

//조상이 같아질 때까지 업데이트
for (int i = COL-1; i >= 0; i--) {
    if (parent[a][i] != parent[b][i]) {
        a = parent[a][i];
        b = parent[b][i];
    }
}

return parent[a][0];

새로운걸 배운다는 생각에 기분이 좀 들떴었는데..
초기화를 잘못해서, 범위를 잘못 설정해서 잡쳤다. 나름 신중하게 수정하고 제출했는데 속상하다😂