LCA 알고리즘(Lowest Common Ancestor)

정의

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

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

접근

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

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

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

노드	레벨	부모 노드
6	6	13
14	4	12

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

노드	레벨	부모 노드
13	5	2
14	4	12

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

노드	레벨	부모 노드
2	4	12
14	4	12

이렇게 수행하면 두 노드의 부모 노드가 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를 사용하였다.