https://www.acmicpc.net/problem/11437
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
www.acmicpc.net
입력을 받은후
1. DFS
입력을 받은뒤, DFS를 돌면서 ( 문제에서 root는 1번노드 ) depth와 부모를 저장해준다.
void dfs(int now, int nowDepth,int prev) {
visit[now] = true; // visit
depth[now] = nowDepth; // 현재 노드의 깊이
par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
for (int i = 0; i < vec[now].size(); i++) {
if (visit[vec[now][i]] == false) {
dfs(vec[now][i], nowDepth + 1,now);
}
}
}2. 부모의 parser_table 생성
반복문으로 parser_table을 생성한다.
주석으로 자세한 설명을 해놓았다.
// 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
// tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
for (int j = 1; j <= 19; j++) {
for (int i = 1; i <= N; i++) {
// i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
// example )
// par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
// par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
// ...
par[i][j] = par[ par[i][j - 1]][j - 1];
}
}3. lca 함수
(주석 참고)
int lca(int x, int y) {
// 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
if (depth[x] > depth[y]) SWAP(x, y);
// y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
// example)
// x와 y가 diff가 5만큼 차이 난다고 가정하면
// y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
// y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
// total 5만큼 높이가 올라가게 된다.
for (int i = 19; i >= 0; i--) {
int diff = depth[y] - depth[x];
if (diff >= (1 << i)) y = par[y][i];
}
// depth를 맞췄는데 같은 노드번호라면 리턴
if (x == y) return x;
// 부모가 같을테까지 같은 depth를 똑같이 올려준다
for (int i = 19; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
// 같아진 부모의 노드번호를 리턴해준다.
return par[x][0];
}전체코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX_N 100001
#define SWAP(a,b) {int t = b; b = a; a = t;}
vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][21];
void dfs(int now, int nowDepth,int prev) {
visit[now] = true; // visit
depth[now] = nowDepth; // 현재 노드의 깊이
par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
for (int i = 0; i < vec[now].size(); i++) {
if (visit[vec[now][i]] == false) {
dfs(vec[now][i], nowDepth + 1,now);
}
}
}
int lca(int x, int y) {
// 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
if (depth[x] > depth[y]) SWAP(x, y);
// y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
// example)
// x와 y가 diff가 5만큼 차이 난다고 가정하면
// y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
// y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
// total 5만큼 높이가 올라가게 된다.
for (int i = 19; i >= 0; i--) {
int diff = depth[y] - depth[x];
if (diff >= (1 << i)) y = par[y][i];
}
// depth를 맞췄는데 같은 노드번호라면 리턴
if (x == y) return x;
// 부모가 같을테까지 같은 depth를 똑같이 올려준다
for (int i = 19; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
// 같아진 부모의 노드번호를 리턴해준다.
return par[x][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N;
for (int i = 0; i < N-1; i++) {
int a, b;
cin >> a >> b;
vec[a].push_back(b);
vec[b].push_back(a);
}
dfs(1, 0, 1);
// 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
// tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
for (int j = 1; j <= 19; j++) {
for (int i = 1; i <= N; i++) {
// i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
// example )
// par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
// par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
// ...
par[i][j] = par[ par[i][j - 1]][j - 1];
}
}
cin >> M;
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
cout << lca(a, b) << "\n";
}
}'알고리즘 > [C++]BOJ' 카테고리의 다른 글
| [백준BOJ] 8012_한동이는 영업사원 (C++) (0) | 2019.10.02 |
|---|---|
| [백준] 2269_수들의합 (C++) (0) | 2019.10.01 |
| [백준] 2336_굉장한 학생 (C++) (0) | 2019.09.30 |
