[Algorithm] 최소 공통 조상 LCA란?

트리 그래프에서 두 노드를 선택했을 때 두 노드가 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상 (LCA, lowest, coomon ancestor)이라고 합니다.

최소 공통 조상 구하기

• 최소 공통 조상을 구하는 아이디어는 각 노드의 깊이를 비교하고 두 노드의 깊이를 같도록 만듭니다.
• 만약 깊이가 같고 값이 다르다면 더 높은 곳으로 올라가야 하기 때문에 두 노드를 같이 부모 노드로 이동합니다.
• 위의 과정을 부모 노드가 같을 때 까지 반복합니다.

1. BFS, DFS를 통해서 각 노드의 부모 노드와 깊이를 담는 배열을 완성합니다. (인접 리스트)

    static void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    q.add(x);
                    V[x] = true;
                    D[0][x] = now;
                    D[1][x] = D[1][now] +1;
                }
            }
        }
    }

위의 코드는 각 노드를 돌면서 깊이와 자신과 연결된 부모 노드를 구해주었습니다.
BFS의 시작 노드는 트리의 루트 노드입니다.

2. LCA

    public static int LCA(int a, int b){
        if(D[1][a] > D[1][b]){
            int temp = b;
            b = a;
            a = temp;
        }
        while (D[1][a] != D[1][b]){
            b = D[0][b];
        }
        while (a != b){
            a = D[0][a];
            b = D[0][b];
        }
        return a;
    }

저는 b의 깊이가 항상 더 깊도록 a와 b를 스왑해주었습니다.
그 후, a와 b의 깊이를 똑같이 맞춰주었고 a와 b가 같을 때 까지 while(a ≠ b) 문을 반복해주었습니다.