mojo's Blog
[백준 11438] LCA 2 본문
문제 링크 => 11438번: LCA 2 (acmicpc.net)
트리를 이용한 최소 공통 조상을 찾는 문제이다.
이문제는 LCA 11437번: LCA (acmicpc.net) 이 문제와 다르게 N 값이 100,000으로 주어졌다.
따라서 1차원 배열로 해결할 경우 시간 초과가 발생한다.
따라서 부모배열을 1차원 배열이 아닌 2차원 배열로 변경하여 parent[x][y] 로 수정해준다.
parent[x][y] => x의 노드에서 2^y 위에 존재하는 부모의 노드이다.
예를 들어서 노드가 다음과 같이 연결된걸로 가정한다.
ex) 1 => 2 => 4 => 8 => 16 => ... => 2^n 일 때,
parent[16][0] = 8 <= 노드 16의 2^0 위에 있는 부모 노드는 8
parent[16][1] = 4 <= 노드 16의 2^1 위에 있는 부모 노드는 4 ( 노드 8의 2^0 위에 있는 부모 노드 )
parent[16][2] = 2 <= 노드 16의 2^2 위에 있는 부모 노드 ( 노드 8의 2^1 위에 있는 부모 노드 = 노드 4의 2^0 위에 있는 부모 노드 )
...
이 규칙을 일반화한다면 다음과 같은 식을 얻는다.
parent[x][y] = parent[parent[x][y-1]][y-1]
그렇다면 2차원 배열 parent를 통해 어떻게 최소 공통 조상을 찾는지에 대해서 다음 방법을 살펴보도록 한다.
- depth[x] > depth[y] 가 되도록 하는 노드 x, y를 설정한다. (LCA와 동일)
- depth[x] == depth[y] 가 되도록 하기 위해 depth[y] - depth[x] >= 2^i 즉, 차이가 발생하는 경우 y = parent[y][i] 를 해줘서 2^i 번째 노드로 이동시켜주는 작업을 한다. ( i = 20, 19, ... , 0 역순으로 진행해야 함 )
- 이때 x == y 인 경우 먼저 반환한다.
- x != y 인 경우 depth[x] == depth[y] 임을 이용해서 parent[x][i] != parent[y][i] 일 때, x = parent[x][i], y = parent[y][i] 를 해줌으로써 x, y의 2^0 위에 있는 부모 노드가 동일해질때까지 진행하고 parent[x][0] 을 반환한다.
풀이 code
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009
#define ll long long
using namespace std;
vector<int> v[100001];
bool visited[100001];
int parent[100001][21];
int depth[100001];
int n;
void compose_Parent(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int mom = q.front();
q.pop();
for (int i = 0; i < v[mom].size(); i++) {
int child = v[mom][i];
if (!visited[child]) {
visited[child] = true;
parent[child][0] = mom;
depth[child] = depth[mom] + 1;
q.push(child);
}
}
}
for (int i = 1; i < 21; i++) {
for (int j = 1; j <= n; j++) {
parent[j][i] = parent[parent[j][i - 1]][i - 1];
}
}
}
int LCA(int x, int y) {
if (depth[x] > depth[y]) {
swap(x, y);
}
for (int i = 20; i >= 0; i--) {
if (depth[y] - depth[x] >= pow(2, 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];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
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);
}
compose_Parent(1);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
cout << LCA(x, y) << endl;
}
return 0;
}
'백준 > Graph' 카테고리의 다른 글
[백준 6543] 그래프의 싱크 (0) | 2021.07.26 |
---|---|
[백준 1761] 정점들의 거리 (0) | 2021.07.20 |
[백준 11437] LCA (0) | 2021.07.20 |
[백준 19535] ㄷㄷㄷㅈ (0) | 2021.07.17 |
[백준 13911] 집 구하기 (0) | 2021.07.06 |
Comments