(백준 c++)11437 LCA

문제

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

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

입력

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

출력

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

 

 

www.youtube.com/watch?v=O895NbxirM8

LCA에 대한 알고리즘을 나동빈님의 영상으로 참고하였다..!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//노드 정보
vector<vector<int>> node(50001);
//부모 노드의 정보
vector<int> parent(50001);
//각 노드의 깊이
vector<int> depth(50001);
// 각 노드의 방문 여부
vector<bool> visited(50001);


//각 노드의 depth 구하기
void dfs(int start, int dpt){
    visited[start] = true;
    depth[start] = dpt;

    for(int i = 0; i < node[start].size(); i++){
        if(visited[node[start][i]]){
            continue;
        }
        parent[node[start][i]] = start;
        dfs(node[start][i], dpt + 1);
    }
}

//LCA 찾기
int lca(int a, int b){
    //a와 b의 depth가 같을 때까지 노드 이동
    while(depth[a] != depth[b]){
        if(depth[a] > depth[b]){
            a = parent[a];
        }
        else{
            b = parent[b];
        }
    }

    //동일한 depth에서 공통 조상 찾기
    while(a != b){
        a = parent[a];
        b = parent[b];
    }

    return a;
}

int main(void){
    int N, M;

    cin >> N;

    for(int i = 1; i < N; i++){
        int n1, n2;
        cin >> n1 >> n2;
        
        node[n1].push_back(n2);
        node[n2].push_back(n1);
    }

    //루트는 1이기 때문에 1부터 시작하여 각 노드의 depth 구하기
    dfs(1, 0);

    cin >> M;

    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }

    return 0;
}