백준 11437 - LCA(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11437

11437번: LCA

최소 공통 조상을 물어보는 문제였습니다.

연결된 노드가 주어졌을 때, 두 노드의 최소 공통 조상을 구하는 문제입니다.

 

문제에서 N과 M이 크기 때문에, 조상을 구하는 과정을 반복하면 시간초과가 생기게 됩니다.

따라서 트리를 만든 뒤, 깊이를 통해 조상을 구하는 방식을 사용해야합니다.

 

트리를 만드는 코드입니다.

void make_tree(){
    queue<int> q;
    q.push(1);
    check[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = 1;
                depth[xx] = depth[x] + 1;
                parent[xx] = x;
                q.push(xx);
            }
        }
    }
}

루트가 1번이라고 주어졌기 때문에, 1번부터 탐색을 시작해 자신과 연결된 노드를 찾아나가야 합니다.

자신과 연결된 노드를 확인한 뒤, 이전에 방문한 적이 없다면 새롭게 나타난 노드라는 의미입니다.

 

따라서 해당 노드의 깊이를 현재 노드의 값에서 1을 더해준 뒤, 부모로 저장해줍니다.

(X에서 XX를 처음 방문했다면, X가 XX의 부모라는 의미이며, XX의 깊이는 X에서 1 더한 값이 됩니다.)

 

 

트리를 구했다면, 이제 두 노드의 공통 조상을 구해야합니다.

void solve(){
    //node2가 node1보다 더 깊은 노드로 만듦
    if(depth[node1] > depth[node2]) swap(node1, node2);
    //같은 깊이로 만듦
    while(depth[node1] != depth[node2]) node2 = parent[node2];
    //두 노드가 같아질 때가지 올라감
    while(node1 != node2){
        node1 = parent[node1];
        node2 = parent[node2];
    }
    cout << node1 << "\n";
}

두 노드는 다른 깊이일 수 있습니다. 

따라서, node2를 항상 더 깊은 노드로 저장해 준 뒤, 같은 깊이로 맞춰줍니다.

같은 깊이로 맞춰주는 이유는 두 노드의 공통 조상은 항상 같은 깊이이기 때문입니다.

 

 X 깊이 일 때, 서로의 조상이 다르다면, 하나씩 올라가면서 같은 노드를 찾아갑니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
int check[50001]; // 이전에 방문했는지
int parent[50001]; // X번 노드의 부모를 저장
int depth[50001]; // X번 노드가 깊이가 어느정도 인지 저장
vector<int> connect[50001];
int node1, node2;

void make_tree(){
    queue<int> q;
    q.push(1);
    check[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = 1;
                depth[xx] = depth[x] + 1;
                parent[xx] = x;
                q.push(xx);
            }
        }
    }
}

void solve(){
    //node2가 node1보다 더 깊은 노드로 만듦
    if(depth[node1] > depth[node2]) swap(node1, node2);
    //같은 깊이로 만듦
    while(depth[node1] != depth[node2]) node2 = parent[node2];
    //두 노드가 같아질 때가지 올라감
    while(node1 != node2){
        node1 = parent[node1];
        node2 = parent[node2];
    }
    cout << node1 << "\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i < N; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    make_tree();
    cin >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> node1 >> node2;
        solve();
    }
    return 0;
}

 

 

자세한 것은 코드를 참고해주세요