[백준] 최소공통조상 LCA 11437번 (C++)

 

https://www.acmicpc.net/problem/11437

 

 

이 문제는 트리가 주어졌을때 두 노드를 기준으로 최소공통 조상을 찾는 문제이다.

최소공통조상 문제는 두 노드 사이의 거리를 빠르게 구하는 방법에서 자주 사용되는 문제이며 

다이나믹 프로그래밍을 사용하여 문제를 해결할 수 있다.

 

아래 예제를 통해 확인해보면

 

 

최소 공통 조상을 찾기 위한 방법으로

 

1. 기본적으로 트리 구조이기 때문에 dfs를 사용하여 노드의 부모를 저장한다.

2. 이후 두 노드를 기준으로 부모가 같아질때까지 계속해서 호출한다. 

 

이렇게 하면 같은 조상을 찾을 수 있다. 하지만 만약 같은 depth(깊이)에 있지 않고

다른 깊이에 있다면 얘기가 달라진다.

 

아래 그림을 한번 살펴보자

 

 

노드 12, 15를 기준으로 최소공통조상을 찾는다고 가정하면 답이 달라질 것이다. 만약 루트1의 부모가 1이라고 한다면

다른 깊이의 공통조상을 찾는다면 계속 1로 출력된다.

 

12노드가 2를 호출할 때 15노드가 4를 호출하기 때문에 최소 공통 조상을 찾을 수 없게 된다.

 

따라서 깊이를 저장하는 배열을 추가하면 이 문제를 쉽게해결할 수 있다.

 

1. 깊이가 다른 경우 더 깊은 깊은 노드를 1씩 낮추며 부모를 호출한다.

2. 두 노드가 같은 깊이(detph)일 경우 부모가 같아질때까지 부모를 호출한다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N, M;
vector<vector<int>> v(50001);
int parent[50001], lv[50001];

void dfs(int Node, int depth, int par) {			// 노드, 깊이, 부모
    lv[Node] = depth;
    parent[Node] = par;

    for(auto it : v[Node]) {
        if(it == par) continue;						// 이전 노드는 탐색했기 때문에 건너뜀
        dfs(it, depth+1, Node);
    }
}

void solve() {
    dfs(1, 0, 0);

    cin >> M;

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

        int l_depth = lv[a], r_depth = lv[b];

        while(l_depth > r_depth) {		// 왼쪽 노드깊이가 더 클 경우 올라가면서 깊이를 맞추기
            a = parent[a];
            l_depth--;
        }

        while(l_depth < r_depth) {		// 오른쪽 노드 깊이가 더 클 경우 올라가면서 깊이를 맞추기
            b = parent[b];
            r_depth--;
        }

        while(a != b) {					// 깊이가 같고 최소 공통 조상을 찾기 위해서 부모를 계속 호출
            a = parent[a];
            b = parent[b];
        }

        cout << a << endl;
    }
}

void input() {
    cin >> N;

    for(int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}