LCA

LCA(Lowest Common Ancestor)

- 개념: 트리에서 두 개의 정점를 선택하였을 때 최소 공통 조상(가장 가까운 공통 조상)을 찾는 알고리즘

- 구현방법

  정점의 깊이를 저장하는 배열 depth[i] = i번 정점의 깊이

  각 정점의 부모를 저장하는 배열 parent[i] = i번 정점의 부모         있다고 할때

 1. 간단한 방법 : 

    ① 두 정점 중 깊이가 더 깊은 정점를 찾아, 깊이가 같아질 때까지 그 정점의 부모로 계속 이동한다.

ex) 정점 A, 정점 B

     if depth[A] > depth[B] // A정점이 깊이가 더 깊음

         while(depth[A] != depth[B]) 

A = parent[A]

    ② 높이가 같아졌다면, 두 정점이 같아질 때까지 두 정점을 동시에 부모로 이동한다.

while(A!=B)

A = parent[A]

B = parent[B]

   -> 이는 공통 조상을 찾을 때 계속 한 정점씩 위로 올라가며 찾다보니

 최악의 경우 O(N)시간이 걸릴 수 있다.

 2. 시간절약 방법 : DP를 사용

    기본적인 방법은 1 방법과 똑같지만, 공통 조상을 찾을 때 좀 더 빨리 이동하는 방법을 사용.

    i번 정점의 부모를 저장하는 배열을 변화시켜 한 정점씩 위로 올라가며 부모(조상)찾기보단 2^k만큼 위로 올라간다.

    -> 최악의 경우 O(logN) 시간 

점화식

parent[i][k] = 정점 i의 2^k 번째 부모

parent[i][k+1] = parent[parent[i][k]][k]

 // 따라서 bottom-up방식을 통해 parent배열을 채워준 후, parent 배열을 통해 빠르게 부모를 찾는다.

- 구현 문제

[백준] 11438번 LCA2

문제

---

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

---

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

---

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

풀이)

간단한 방법으로 풀면 시간 초과가 나는 문제다. dp를 이용해서 풀어야한다.

코드)

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
 
#define MAX 18 //log1000000 = 16.6... 
int N, M;
int parent[100001][MAX]; //각 정점의 2^k 번째 부모 저장
int depth[100001]; //각 정점의 깊이 저장
vector<int> adj[100001];
 
void dfs(int here) {
    for (int i = 0; i < adj[here].size(); i++) {
        int next = adj[here][i];
        if (depth[next] == -1) {
            parent[next][0] = here;
            depth[next] = depth[here] + 1;
            dfs(next);
        }
    }
}
int main() {
    scanf("%d", &N);
    int n1, n2;
    int p1, p2;
    int common;
 
    for (int i = 1; i < N; i++) {
        scanf("%d %d", &n1, &n2);
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
 
        depth[i] = -1;
    }
    //1번부터 N번까지 depth = -1로 초기화
    for (int i = 1; i <= N; i++) {
        depth[i] = -1;
    }
    memset(parent, -1, sizeof(parent));
 
 
    depth[1] = 0;//트리 맨 위의 root를 1번 정점이라하고, 그 정점의 depth = 0 으로 초기화
    dfs(1); //트리만듬. 깊이도 저장하면서
 
    //배열채움 bottom-up
    for (int k = 0; k < MAX - 1; k++) {
        for (int i = 2; i <= N; i++) { //2번 노드부터
            if (parent[i][k] != -1) {
                parent[i][k + 1] = parent[parent[i][k]][k];
            }
        }
    }
 
    scanf("%d", &M);
    for (int i = 1; i <= M; i++) {
        scanf("%d %d", &n1, &n2);
        //깊은 depth를 가진것을 n1으로
        if (depth[n1] < depth[n2]) swap(n1, n2);
 
        //n1정점를 n2정점와 같은 depth를 가질때까지 n1정점을 위로 올리기(부모찾기)
        //빨리 이동하기 위해 2^17부터 큰값부터
        for (int i = MAX - 1; i >= 0; i--) {
            if (depth[n1] - depth[n2] >= (1 << i)) {
                n1 = parent[n1][i];
            }
        }
 
        //두 정점이 같은 높이를 가졌을 때 n1과 n2가 같을시
        if (n1 == n2) {
            printf("%d\n", n1);
            continue;
        }
        //두 정점의 같은 높이를 가졌음에도 다르다면 n1, n2 동시에 일정 높이만큼 위로이동
        //빨리 이동하기 위해 큰값부터
        for (int i = MAX - 1; i >= 0; i--) {
            if (parent[n1][i] != -1 && parent[n1][i] != parent[n2][i]) {
                n1 = parent[n1][i];
                n2 = parent[n2][i];
            }
        }
 
        printf("%d\n", parent[n1][0]);
    }
    return 0;
}

참고블로그)

https://www.crocus.co.kr/660

https://m.blog.naver.com/kks227/220820773477