BOJ 11438

13 Feb 2020 • ProblemSolving

LCA 2

문제출처

문제 해석

  • 주어진 트리로 M개의 공통조상을 찾는 문제입니다.

설계(X)

  • LCA(Lowest Common Ancestor) 알고리즘을 배워보지 않았기 때문에 crocus님이 올리신 블로그를 통해서 알고리즘을 익히게 되었습니다.
  • LCA란 두개의 정점이 가지는 같은 조상중에 최고로 가까운 조상들을 찾는 알고리즘입니다.
  • LCA를 찾을 때 쓰이는 알고리즘은 여러가지가 있지만 세그먼트 트리또는 DP를 많이 이용합니다.
  • 여기서는 DP로 구현하셨습니다.
  • LCA를 구현하기 위해서 다음의 과정을 거칩니다.
    1. DFS를 이용하여 트리를 생성하는(O(N)) 과정에서 각 정점의 2n부모를 저장합니다. 또한, 각 정점의 높이(depth)를 저장합니다.
      • 여기서 2n부모란 어떠한 조상으로 부터 내려온 자신을 기준으로 했을 때, depth-n 높이에 있는 조상을 뜻합니다.
      • 이를 구하기 위해서 par[x][i] = par[par[x][i-1]][i-1] (x: 현재 노드, i: 2^n번째 조상) 점화식을 이용합니다.
    2. 트리를 완성했으면, 주어진 두 노드(a,b)의 LCA(a,b)를 찾기 위해서 a의 높이와 b의 높이를 비교해서 같은 높이가 오도록 맞춰줍니다.
      • 여기서 a와 b중 깊은 노드를 낮은 노드와 같게 맞춰주는데 만약 더 깊은게 b라고 예를 들면, b의 n번째 조상부터 순차적으로 내려오면서 깊이가 더 깊은 노드가 나올 때 해당 노드로 업데이트를 해줍니다.
      • 만약 더 얕은 깊이가 나오면 업데이트를 하지 않습니다.
    3. 두 노드의 깊이를 같게 만들었으면, 각 두 노드의 조상들을 바라보면서 같은 조상이 나올때까지 반복하게 됩니다.
  • 위 과정들을 거치면 LCA를 찾을 수 있게 됩니다.

구현(X)

코드
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>

#define INF 987654321
#define MAXN 100000 + 1
using namespace std;
#define swap(a,b){int t= a; a= b; b = t;}
typedef pair<int,int> pii;
int depth[MAXN];
int ac[MAXN][20];

int N,M;
vector<int> adj[MAXN];
int max_level;
void getTree(int here, int parent){
    depth[here] = depth[parent]+1;
    ac[here][0] = parent;
    max_level =(int)floor(log2(MAXN));
    for (int i = 1; i <=max_level; i++){
        ac[here][i] = ac[ac[here][i-1]][i-1];
    }
    for (int i = 0 ;i < adj[here].size(); i++){
        int there = adj[here][i];
        if (there != parent){
            getTree(there,here);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0 ;i < N-1; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    depth[0] = -1;
    getTree(1,0);
    cin >> M;
    while (M--){
        int a,b;
        cin >> a >> b;
        if (depth[a] != depth[b]){
            if (depth[a] > depth[b]) swap(a,b);
            // depth[b] >= depth[a] 될때까지
            for (int i = max_level; i >=0; i--){
                // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 b의 조상을 계속 타고 올라간다.
                if (depth[a] <= depth[ac[b][i]]){
                    b = ac[b][i];
                }
            }
        }
        int lca = a;
        if (a != b){
            for (int i = max_level; i >=0; i--){
                if (ac[a][i] != ac[b][i]){
                    a = ac[a][i];
                    b = ac[b][i];
                }
                lca = ac[a][i];
            }
        }
        cout << lca <<"\n";
    }
    return 0;
}
디버깅
제출결과

마무리

  • drill이라는 백준그룹에 참가하여 2주동안 알고리즘 풀이를 할 예정입니다. 현재 키워드는 [LCA,구간쿼리]로, 처음 접해보는 어려운 문제입니다. 하지만, 알고리즘 능력을 더욱 향상시키기 위해서는 이러한 어려운 것들도 구현을 해봐야 할 것 같습니다.
 BOJ

Related Posts