백준 11438 - LCA 2

출처 : https://www.acmicpc.net/problem/11438 

11438번: LCA 2

 

고려사항

• lca 알고리즘 문제들을 두 세개 풀어봐서 그 로직을 잘 이해하고 있었는데.....
  맞왜틀의 연속으로 인해 (매우 큰 착각ㅎㅎ) 자꾸 검색하고 참조한 결과
  그냥 쌩 남의 코드랑 똑같아졌다...(그런데 같은 코드가 여러개 보인다..ㅎㅎ)
• 확실하진 않으나 한시간 넘게 고민해본 결과...
  이전의 코드는 dfs 함수 없이 간선의 노드 정보 2개가 들어오면,
  보통 트리 문제에서 순서대로(레벨이 낮은 순서로) 노드에 번호 이름이 붙인다는 착각에 맘대로
  if(a > b) swap(a, b) 해주어 무조건 번호가 작은 노드가 다른 한 쪽의 부모 노드가 된다라고 가정하에
  트리를 구성했다.
  놀랍게도, 게시판 내에 있는 모든 반례, 수동 예제들이 그러한 특성을 만족하는 인풋이 주어져 계속해서
  맞왜틀을 울부 짖고 있었다...그런데 정작 문제에는 그런 조건이 명시되어 있지도 않았고,
  간선 중 첫번째 노드(시작지점)가 더 큰 간선 정보도 있는데 이걸 굳이 swap 해주어
  dfs 과정 없이도 레벨을 구해지게끔 구현했다고 자부심을 느끼고 있던 나 자신을 반성....
• 얻은 지식도 있었다. 이전에는 두 노드간 레벨을 같게 만들어 주는 과정이나 얼마만큼 올라가야 하는지 구하는 과정을
  다소 무식하게 직접 2진수를 구하고, 뒤집다 보니 매우 난해하게 2중 포문으로 구현했었는데,
  36 - 40, 47 - 52 처럼 매우 간편하게 logn 시간 복잡도를 달성할 수 있는 방법을 깨달았다!
• 바로 lca 알고리즘의 핵심 로직이 이 부분이다.
  조사중인 두 노드의 레벨이 같을 때까지 2^n 꼴로 노드를 거슬러 올라가고, ( 36 - 40 )
• 같은 레벨에서 조사 대상인 노드의 2^i 번째 조상이 서로 같으면( 조상이 없을 때도 0으로 같다고 취급!) --i,
  서로 다르면 조사 노드 업데이트를 반복한다. ( 47 - 52 )
• 이런 과정을 반복하면, 결국 최소 공통 조상 바로 1단계 아래 노드들이 두 노드 값이 된다.
  이중 아무거나의 2^0 번째, 즉 한 단계 위의 즉, 최소 공통 조상을 반환해주면 된다!
• 이런 방식을 처음 써봐서 머리로 이해는 대략 된것같은데 확실히 설명하거나 내 코드로 만들기는 아직 무리인것같다^^

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
struct node{
    int level;
    vector<int> child;
};
 
bool visit[100001];
int parent[100001][18];
vector<node> v(100001);
 
void dfs(int node, int lev){
    visit[node] = true;
    v[node].level = lev;
 
    for(int nextNode : v[node].child){
        if(visit[nextNode]){
            continue;
        }
        parent[nextNode][0] = node;
        dfs(nextNode, lev+1);
    }
}
 
int lca(int node1, int node2){
    if(v[node1].level != v[node2].level){
        if(v[node1].level < v[node2].level){
            int tmp = node1;
            node1 = node2;
            node2 = tmp;
        }
 
        for(int i=17;i>=0;--i){
            if(v[node1].level-v[node2].level >= (1 << i)){
                node1 = parent[node1][i];
            }
        }
    }
 
    if(node1 == node2){
        return node1;
    }
 
    for(int i=17;i>=0;--i){
        if(parent[node1][i] != parent[node2][i]){
            node1 = parent[node1][i];
            node2 = parent[node2][i];
        }
    }
 
    return parent[node1][0];
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n, q, p, c, node1, node2;
 
    cin>>n;
    for(int i=1;i<n;++i) {
        cin >> p >> c;
        v[p].child.push_back(c);
        v[c].child.push_back(p);
    }
 
    dfs(1, 0);
 
    for(int j=1;j<=17;++j){
        for(int i=1;i<=n;++i){
            parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }
 
    cin>>q;
    for(int i=0;i<q;++i){
        cin>>node1>>node2;
        cout<<lca(node1, node2)<<"\n";
    }
 
    return 0;
}