최소 공통 조상 알고리즘

1. Problem

- 주어진 트리에서 두 노드 node1, node2의 최소 공통 조상을 찾아보자.

- 최소 공통 조상(Lowest Common Ancestor, LCA)는 특정한 두 노드의 공통된 조상 중 가장 가까운 조상을 말한다.

- 이진 트리가 아니어도 적용되는 알고리즘이다.

- 다이나믹 프로그래밍을 이용하는 알고리즘이다.

 

2. Input

1) int[][] graph

- graph[i][j]: i는 j의 부모 노드

2) int n

- 노드의 개수

3) int node1

4) int node2

 

3. Output

1) node1과 node2의 최소 공통 조상

 

4. Explanation

1) 트리에 있는 모든 노드에 대해서 각 노드의 깊이(depth)를 구한다.

 

2) 모든 노드에 대해서 각 노드의 2^i (i=0,1,2,...)번째 부모 노드를 구한다.

- 예를 들어 18의 2^0번째 조상은 11, 2^1번째 조상은 5, 2^2번째 조상은 0이다.

- 공통 부모를 찾을 때 시간 복잡도가 O(lgn)이 되도록 하기 위함이다.

 

3) 최소 공통 조상을 찾을 두 노드를 확인한다.

- node1 = 16, node2 = 11

 

4) 두 노드의 깊이가 동일해지도록 깊이가 더 깊은 노드가 위로 거슬러 올라온다.

- 여기서는 16이 하나 위로 거슬러 올라온다.

 

5) 두 노드의 공통 부모를 찾는다.

 

5. Code

// 클래스 변수
static final int LOG = 11; // 2^i번째 부모 노드를 찾을 때 i에 사용할 수
                           // 2^10번째 부모까지 커버 가능
static final int MAX = 1025; // 최대 2^10+1개의 노드 저장
static int n; // 노드의 개수
static boolean[] visit = new boolean[MAX]; // i번 노드를 방문했다면 true
static int[][] parent = new int[MAX][LOG]; // i번의 2^0번째, 2^1번째,..., 2^10번째 부모 저장
static int[] depth = new int[MAX]; // i번 노드의 깊이
static List<List<Integer>> tree = new ArrayList<List<Integer>>();
                        // tree.get(i): i번 노드의 자식 리스트

// main()
int node1 = 16, node2 = 11;
n = 19; // 0번~18번 노드
int[][] graph = {{0,1},{1,4},{4,8},{8,15},{4,9},{9,16},{1,5},{5,10},{5,11},{11,17},{11,18},
                 {0,2},{0,3},{3,6},{3,7},{7,12},{7,13},{7,14}};
for(int i=0 ; i<n ; i++) // i번의 자식을 넣을 리스트 생성
    tree.add(new ArrayList<>());
for(int i=0 ; i<graph.length ; i++) // graph[i][j]: i번은 j번의 부모
    tree.get(graph[i][0]).add(graph[i][1]);
setParent();

// 바로 위의 부모와 연결해주는 메서드
static void dfs(int x, int d) {
    visit[x] = true; //
    depth[x] = d;
    for(int y : tree.get(x)) { // x의 자식 노드를 따라가며
        if(visit[y]) continue; // 방문했다면 넘어가고
        parent[y][0] = x;  // 방문하지 않았다면 부모를 x로 저장하고
        dfs(y, d+1);       // y의 자식 노드에 대해서도 dfs를 수행
    }
}
    
// 모든 노드에 대해 부모를 설정해주는 메서드
// 4. Explanation의 2)의 과정
static void setParent() {
    dfs(0, 0); // 노드 0의 깊이를 0으로 설정 -> 0이 최상단 노드(root)
    // 바로 위 부모까지는 연결이 되어 있는 상태
    for(int j=1 ; j<LOG ; j++)   // i번 노드의 2^j번째 부모는 
        for(int i=0 ; i<n ; i++) // i번 노드의 2^(j-1)번째 부모의 2^(j-1)번째 부모
            parent[i][j] = parent[parent[i][j-1]][j-1];	
            // 예를 들어 parent[8][1] = parent[parent[8][0][0] = parent[4][0] = 1
}
    
// 최소 공통 조상을 찾는 메서드
static int LCA(int x, int y) {
    if(depth[x]>depth[y]) { // x의 깊이 < y의 깊이가 되도록 맞추기
        int tmp = x;
        x = y;
        y = tmp;
    }
    
    for(int i=LOG-1 ; i>=0 ; i--) // x, y의 깊이를 동일하게 맞추기
        if(depth[y]-depth[x] >= (1<<i)) // 깊이 차이가 2^i보다 더 크다면
            y = parent[y][i];           // y가 y의 2^i번째 조상으로 거슬러 올라간다.

    if(x==y) return x; // y가 거슬러 올라왔을 때 x가 된다면 x가 최소 공통 조상이다.

    // root부터 내려오며 공통 조상 찾기
    for(int i=LOG-1 ; i>=0 ; i--) // 조상이 같아질 때까지 거슬러 올라간다.
        if(parent[x][i]!=parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    return parent[x][0]; // 조상이 같아졌으므로 해당 조상이 최소 공통 조상이 된다.
}

// 다시 main()
System.out.printf("node1(=%d)과 node2(=%d)의 LCA = %d\n",node1,node2,LCA(node1,node2));
-> node1(=16)과 node2(=11)의 LCA = 1

---

[setParent()의 이해를 돕기 위한 예시의 parent[][]의 값]

static int[][] parent = new int[MAX][LOG]; // i번의 2^0번째, 2^1번째,..., 2^10번째 부모 저장

- 예시의 트리는 최대 깊이가 4이기 때문에 4 = 2^2 -> parent[i][2]까지가 유효한 부모