LCA (최저공통조상)

Lowest Common Ancestor

트리에서 노드 A, B가 가장 처음으로 만나게 되는 노드

• 자기자신도 포함!

두 노드의 Depth를 맞춘 후
1. 같다면 그 노드가 LCA
2. 다르다면 Depth-1

최악의 경우

높이가 H인 경우 O(H)
높이가 N이라면? O(N)

높이 맞추기

하나씩 체크하면 속도가 너무 느리므로
2^n만큼 높이를 거슬러 올라가보자

• 노드 A의 높이를 ha
• 노드 B의 높이를 hb 라고 했을 때

1. 2^0만큼 올라갔을 때 ha + 2^0 > hb 이면 2^1칸 더 올라가본다.
2. 2^1만큼 올라갔을 때의 hb가 ha보다 작으면 계속 올라간다.
3. 2^n만큼 올라갔을 때의 hb - 2^n이 ha보다 작다면
4. 그 전까지 높이로 hb를 갱신한다. hb = hb - 2^(n-1)
5. 1~4의 과정을 반복 후 ha = hb인 높이를 찾는다.

LCA 찾기

6. tree[ha] = tree[hb] 라면 그 값이 LCA
7. 다르다면 ha와 hb의 값이 같아지는 높이, 즉 tree[ha + 2^m] = tree[hb + 2^m]이 되는 m값을 찾는다.
8. ha, hb의 값에 각각 2^(m-1) 을 더한 값으로 갱신한다.
9. 6~8의 과정을 반복한다.

구현하기

1. 조상의 정보를 담을 배열 선언

int[][] Parent = new int[K][V];

Parent[k][v]는 v의 2^k의 부모를 저장할 곳

k가 V보다 작으므로 int[K][V]를 생성하는 것이 int[V][K]를 생성하는 것이 빠름

// N <= 2^LGN
// N이 100000이면 2^17(131072) 이므로 LGN = 17
int LGN = 17;

2. dfs, bfs로 depth를 계산한다.

static void dfs(int idx, int dep) {
    depth[idx] = dep;
    
    for(int next: adjList[idx]) {
    	Parent[0][next] = idx;
        dfs(next, dep+1);
    }
}

static void bfs(int start, int dep) {
    Queue<Integer> q = new ArrayDeque<Integer>();
    depth[start] = dep;
    q.offer(start);
    
    while(!q.isEmpty()) {
    	int cur = q.poll();
        for(int next: adjList[cur]) {
           Parent[0][next] = cur;
           depth[next] = depth[cur] + 1;
           q.offer(next);
        }
    }
}

3. 2^k번째의 조상을 저장한다

static void findParent() {
    for(int K=1; K<LGN; K++) {
    	for(int V=1; V<=N; V++) {
            Parent[K][V] = Parent[K-1][Parent[K-1][V]];
        }
    }
}

4. LCA를 찾는다

static int lca(int x, int y) {
    // depth가 큰 정점을 y로 설정한다.
    if (depth[x] > depth[y]) {
    	int tmp = x;
        x = y;
        y = tmp;
    }
    
    // y의 높이를 맞춘다
    for(int i=LGN; i >= 0; i--) {
    	// 1<<i는 2^i
    	if(depth[y] - depth[x] >= (1<<i)) {
            y = Parent[i][y];
        }
    }
    
    // 높이가 같고 값이 같다면 찾음!
    if(x == y) return x;
    
    // 같지 않다면 루트에서 내려오면서 탐색
    for(int i=LGN; i>=0; i--) {
    	if(Parent[i][x] != Parent[i][y]) {
            x = Parent[i][x];
            y = Parent[i][y];
        }
    }
    
    // 처음으로 달라진 위치의 부모가 공통조상
    return Parent[0][x];
}