[백준][C++] 11437 LAC(lowest Common Ancester)

www.acmicpc.net/problem/11437

11437번: LCA

 

 

 

알고리즘 종류

트리

LCA

 

 

 

사고 과정

1. 인접행렬로 노드 쌍을 받아습니다. 그리고 depth과 parents 배열로 트리를 만들어 줍니다.

 

2. 공통 부모를 찾을 두 노드를 받습니다. 두 노드의 깊이가 같아질 때까지 부모를 타고 올라갑니다. 두 노드가 같은 깊이에 도달하면, 동시에 타고 올라가면서 공통 부모가 될때까지 올라갑니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
 
using namespace std;
 
int n, m;
 
int parents[50001];
int depth[50001];
vector<int> edges[50001];
 
 
void make_tree(){
    
    queue<int> q;
    q.push(1);
    depth[1] = 1;
    parents[1] = 1;
    
    while(!q.empty()){
        int node = q.front();
        q.pop();
        
        for(int i=0; i<edges[node].size(); i++){
            int next_node = edges[node][i];
            if(depth[next_node]) continue;
            depth[next_node] = depth[node] + 1;
            parents[next_node] = node;
            q.push(next_node);
        }
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n;
    
    int u, v;
    for(int i=0; i<n-1; i++){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    
    make_tree();
    
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> u >> v;
        
        // 두 노드의 깊이가 같아질 때까지 부모를 타고 이동
        while(depth[u] > depth[v]){
            u = parents[u];
        }
        
        while(depth[u] < depth[v]){
            v = parents[v];
        }
        
        // 같은 깊이일 때, 동시에 부모를 타고 올라가면서 부모가 같아질 때까지 이동
        while(u != v){
            u = parents[u];
            v = parents[v];
        }
        
        cout << u << endl;
    }
}
 

 

 

 

시행착오