LCA 알고리즘(Lowest Common Ancestor)

정의

최소 공통 조상을 찾는 알고리즘
즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘이다.

다음과 같은 그래프에서 6과 9 노드의 최소 공통 조상은 2이다.
마찬가지로, 10과 4의 최소 공통 조상은 8이 된다.

접근

최소 공통 조상을 찾는 방법은 각 노드에서 부모를 타고 올라가서 같은 부모를 찾으면 될 것이다.
하지만 이 때, 양 노드의 LEVEL이 같아야 이러한 방법으로 접근할 수 있다.

결과적으로, 각 노드의 부모와 레벨을 알아야 한다.
필요한 것은 각 노드의 부모와 레벨, 그리고 트리이다.

깊이와 부모를 저장한 상태로 있다고 가정하고, 6과 14의 공통조상을 구해보면,
루트 노드의 레벨을 1이라 하면, 노드 6의 레벨은 6, 14의 레벨은 4이다.

노드 6의 레벨이 더 크니, 레벨을 맞춰주기 위해 노드 6의 부모로 바꿔준다.

같은 작업을 한번 더 수행한다.

이렇게 수행하면 두 노드의 부모 노드가 12로 같은 것을 알 수 있다.
만약 여기서 부모 노드가 다르다면, 같을 때 까지 양 노드를 부모 노드로 바꿔주면 될 것이다.

그럼 어떻게?

각 노드의 부모 노드와 레벨을 저장하는 방법은 어떻게 할 까?
DFS를 돌면서 저장할 수 있다.
재귀를 한번씩 돌 때 마다 레벨이 1씩 올리면서 저장하고, 부모 노드 또한 저장할 수 있다.

예제 문제와 코드 - JAVA

다음 문제는 백준 11437번 LCA 문제이다.

import java.io.*;
import java.util.*;

public class Main {

    static ArrayList<Integer>[] tree;
    static int[] parents;
    static int[] depths;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int inputCnt = Integer.parseInt(br.readLine());
        tree = new ArrayList[inputCnt+1];
        for (int i = 1; i <= inputCnt; i++) {
            tree[i] = new ArrayList<Integer>();
        }
        parents = new int[inputCnt+1];
        depths = new int[inputCnt+1];
        Arrays.fill(depths,-1);
        StringTokenizer st;
        for(int i=0; i<inputCnt-1; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree[a].add(b);
            tree[b].add(a);
        }
        
        dfs(1,1,0);//레벨 및 부모 노드 저장
        
        int caseCnt = Integer.parseInt(br.readLine());
        for(int i=0; i<caseCnt; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            int result = LCA(a,b);
            
            bw.write(String.valueOf(result));
            bw.newLine();
        }
        bw.flush();
        bw.close();
        br.close();
    }
    
    public static int LCA(int a, int b){
        int aDepth = depths[a];
        int bDepth = depths[b];
        while(aDepth>bDepth){
            a = parents[a];
            aDepth--;
        }
        while(bDepth>aDepth){
            b = parents[b];
            bDepth--;
        }
        while(a!=b){
            a = parents[a];
            b = parents[b];
        }
        return a;
    }

    public static void dfs(int current, int depth, int parent){
        depths[current] = depth;
        parents[current] = parent;
        for(int nextNode : tree[current]){
            if(nextNode != parent){
                dfs(nextNode,depth+1,current);
            }
        }
    }
}

출력이 많아 BufferWriter를 사용하였다.