알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor)

알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor)

정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라 갈 때 처음 공통으로 만나게 되는 정점이다. 정점 A혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다.

8과 9의 공통 조상들은 1, 2, 4 / 8과 9의 최소 공통 조상은 4

3과 6의 공통 조상들은 1, 3 / 3과 6의 최소 공통 조상은 3

8과 5의 공통 조상들은 1, 2 / 8과 5의 최소 공통 조상은 2

 

[ 최소 공통 조상 구하기 ]

- 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다.

- 정점의 부모를 따라 하나씩 올라가 LCA를 찾는다.

시간복잡도 : 트리의 깊이를 H라 할 때, 시간복잡도는 O(H), 최악의 경우 O(N)

 

[ 최소 공통 조상 빠르게 구하기 ]

- 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 조상 뿐만 아니라 2^K번째 조상까지 저장한다.

- 먼저 서로 다른 깊이를 가지는 노드를 같은 깊이를 가지는 노드로 만들어준다.

- 2^K 만큼씩 조상을 올려다보며 조상이 같아질 때 까지 노드를 타고 올라가서 LCA를 구한다.

 

parent[K][V] : 정점 V의 2^k번째 조상의 정점 번호

parent[K][V] = parent[K-1][parent[k-1][V]]

시간복잡도 : 트리의 깊이를 H라 할 때, 시간복잡도는 O(logH), 최악의 경우 O(logN)

 

[ 코드 ]

int lca(int x, int y) {
    if (d[x] > d[y])
        swap(x, y); //깊이 맞추는 과정
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (1 << i)) 
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}


출처: https://jason9319.tistory.com/90 [ACM-ICPC 상 탈 사람]

 

참고 사이트

www.crocus.co.kr/660

jason9319.tistory.com/90#:~:text=%EB%8B%A4%EC%9D%8C%EA%B3%BC%20%EA%B0%99%EC%9D%80%20%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C,%EB%A5%BC%20%EB%B3%B4%EA%B2%8C%20%EB%90%A0%20%EA%B2%83%EC%9E%85%EB%8B%88%EB%8B%A4.