[백준,c++] 11437번 - LCA

문제

11437번: LCA

 

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int>graph[50001];
int depth[50001];
int parent[50001];
bool visited[50001];


void dfs(int node, int _depth){
    visited[node] = 1;
    depth[node] = _depth;
    for(auto next: graph[node]){
        if(!visited[next]){
            parent[next] = node;    // 부모 세팅
            dfs(next, _depth + 1);
        }
    }
}

int lca(int a, int b){
    while(parent[a]!=parent[b]){    // 부모가 다를 경우
        if(depth[a] < depth[b]){    // 높이를 맞춰준다(높이가 긴 쪽을 적게한다.)
            b = parent[b];
        }
        else a = parent[a];
    }
    while(a!=b){
        a = parent[a];
        b = parent[b];
    }
    return a;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N-1; i++){
        int a, b; cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1, 0); // depth 저장하기
    cin>>M;
    
    
    for(int i=0; i<M; i++){
        int a, b; cin>>a>>b;
        cout<< lca(a,b)<<'\n';
    }
}

 

풀이

LCA(최소 공통 조상) 문제입니다.

[백준,c++] 3584번 - 가장 가까운 공통 조상

이 문제와 다른 점은 공통 조상을 찾는 쿼리가 여러 개가 주어진다는 점입니다.

나동빈 님의 위 영상을 보면 쉽게 이해가 가능합니다.

• dfs를 돌려 각 노드의 부모와 깊이를 기억합니다.
• 공통 부모를 조사할 두 노드의 높이를 맞춰줍니다.
• 부모를 찾습니다.