백준 11438번 (LCA 2) C++

문제

11438번: LCA 2

N개의 트리 정점이 주어지고 두 노드의 쌍 M개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇번인지

출력하는 문제입니다.

 

naive하게 생각하면 시간복잡도가 O(N)이므로 범위가 커지게 되면 시간초과가 나게 됩니다.

따라서 Sparse Table 알고리즘 방식을 사용하였습니다.

 

먼저 par[x][y] = x노드의 2^y 부모 라는 배열을 정의합니다.

다음에 depth배열을 정의해줍니다. depth배열은 노드의 깊이를 저장한 배열입니다.

LCA알고리즘을 활용하기 위해서는 각 노드의 깊이가 서로 같아야 합니다.

따라서 각 노드의 깊이를 먼저 파악하고 깊이를 먼저 서로 맞춰주고 알고리즘을 진행하여야합니다.

---

void dfs(int x, int par) {
    depth[x] = depth[par] + 1;
        for (int nxt : v[x]) {
            if (nxt == par)continue;
            parent[nxt][0] = x;
            dfs(nxt, x);
        }
}

각 노드의 깊이를 알기위해 DFS를 활용해 주어서 진행하였습니다.

---

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

parent배열을 전처리하는 과정입니다. 

sparse table의 전처리 과정과 동일합니다.

---

int lca(int x, int y) {
    if (depth[x] > depth[y])swap(x, y);//항상 y의 깊이가 더 깊게 만들자
    for (int i = 20; i >= 0; i--) //y를 x의 깊이만큼 올려주는 작업
        if (depth[y] - depth[x] >= (1 << i))
            y = parent[y][i];
    if (x == y)return x; //둘이 같은 노드 일때(예외 처리)
    for (int i = 20; i >= 0; i--) {
        if (parent[x][i] != parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    return parent[x][0]; //parent[y][0] 으로 해도된다
}

7-13 번째 줄을 보면 각각이 노드의 부모노드를 

2^20 부터 1까지 올라가면서 확인할것입니다.

두 노드의 부모노드가 서로 같지 않을때 

return 해주면 됩니다.

왼쪽 그림에서는 2^0번째 부모노드가 같지 않으므로 

각각의 노드는 2와 3으로 올라가게 됩니다.

마지막에 parent[2][0] 또는 parent[3][0]을 return 하면

두 노드의 최소 공토 부모노드를 찾게 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, m, parent[100001][21], depth[100001], a, b;
vector<int>v[100001];
void dfs(int x, int par);
int lca(int x, int y);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    for (int i = 1; i < 21; i++)
        for (int j = 1; j <= n; j++)
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}
void dfs(int x, int par) {
    depth[x] = depth[par] + 1;
        for (int nxt : v[x]) {
            if (nxt == par)continue;
            parent[nxt][0] = x;
            dfs(nxt, x);
        }
}
int lca(int x, int y) {
    if (depth[x] > depth[y])swap(x, y);//항상 y의 깊이가 더 깊게 만들자
    for (int i = 20; i >= 0; i--) //y를 x의 깊이만큼 올려주는 작업
        if (depth[y] - depth[x] >= (1 << i))
            y = parent[y][i];
    if (x == y)return x; //둘이 같은 노드 일때
    for (int i = 20; i >= 0; i--) {
        if (parent[x][i] != parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    return parent[x][0]; //parent[y][0] 으로 해도된다
}