https://www.acmicpc.net/problem/3584
3584번: 가장 가까운 공통 조상
루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두
www.acmicpc.net
LCA 알고리즘을 연습해볼 수 있는 간단한 문제입니다.
다만 이 문제는 방향 그래프이고, 루트가 정해져 있습니다.
저는 루트 확인을 chk 배열로 확인하였고, 입력이 자식으로 들어오지 않은 노드를 루트로 지정해주었습니다.
그리고 구했던 root를 시작으로 dfs를 돌려 각 노드의 depth를 구해주면서 자신들의 부모노드를 저장해줍니다. (parent[next][0] = v)
이제 자신의 2^n번째 조상을 모두 구하여 lca알고리즘으로 가장 가까운 공통 조상을 출력해줍니다.
이 문제는 입력이 10000개이므로 lca를 사용하지 않아도 풀리는 문제입니다.
자신의 부모만 구하여 최소 공통 조상을 구하는 방법인데 u, v의 높이를 같게 맞춘 다음 부모가 같아질때까지 한칸씩 위로 올리는 방식입니다.
소스 같이 올리겠습니다.
이 문제는 입력 범위가 작아서 그런지 시간은 동일하게 나왔습니다.
[LCA 사용]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
#define LOG 15
using namespace std;
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1][LOG];
int N, s, e, root;
void dfs(int v, int d) {
depth[v] = d;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
if (depth[next]) continue;
parent[next][0] = v;
dfs(next, d + 1);
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; i--) {
if (depth[v] - depth[u] >= (1 << i)) {
v = parent[v][i];
}
}
if (u == v) return u;
for (int i = LOG - 1; i >= 0; i--) {
if (parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
return parent[v][0];
}
void func() {
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= N; i++) {
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
}
cout << lca(s, e) << '\n';
}
void input() {
int u, v;
cin >> N;
for (int i = 0; i < N - 1; i++) {
cin >> u >> v;
graph[u].push_back(v);
chk[v] = true;
}
for (int i = 1; i <= N; i++) {
if (!chk[i]) {
root = i;
break;
}
}
cin >> s >> e;
}
void init() {
memset(depth, 0, sizeof(depth));
memset(parent, 0, sizeof(parent));
memset(chk, false, sizeof(chk));
for (int i = 1; i <= N; i++) graph[i].clear();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
dfs(root, 1);
func();
init();
}
return 0;
}
|
cs |
[LCA 사용X]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <iostream>
#include <vector>
#include <cstring>
#define MAX 10000
using namespace std;
vector<int> graph[MAX + 1];
bool chk[MAX + 1];
int depth[MAX + 1];
int parent[MAX + 1];
int N, s, e, root;
void dfs(int v, int d) {
depth[v] = d;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
if (depth[next]) continue;
parent[next] = v;
dfs(next, d + 1);
}
}
int func(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
while (depth[u] != depth[v]) {
v = parent[v];
}
if (u == v) return u;
while (parent[u] != parent[v]) {
u = parent[u];
v = parent[v];
}
return parent[u];
}
void input() {
int u, v;
cin >> N;
for (int i = 0; i < N - 1; i++) {
cin >> u >> v;
graph[u].push_back(v);
chk[v] = true;
}
for (int i = 1; i <= N; i++) {
if (!chk[i]) {
root = i;
break;
}
}
cin >> s >> e;
}
void init() {
memset(depth, 0, sizeof(depth));
memset(parent, 0, sizeof(parent));
memset(chk, false, sizeof(chk));
for (int i = 1; i <= N; i++) graph[i].clear();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
dfs(root, 1);
cout << func(s, e) << '\n';
init();
}
return 0;
}
|
cs |
'algorithm > LCA' 카테고리의 다른 글
| boj 6059 Pasture Walking (0) | 2021.06.16 |
|---|---|
| boj 1626 두 번째로 작은 스패닝 트리 (0) | 2021.04.02 |
| boj 15481 그래프와 MST (0) | 2021.04.01 |
| boj 15480 LCA와 쿼리 (0) | 2021.02.14 |
| boj 11438 LCA 2 (0) | 2021.02.11 |