1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
두 가지 방법으로 해결하였습니다. 하나는 union-find를 이용한 방법, 하나는 dfs를 이용한 방법입니다.
먼저 union-find 방법입니다.
입력에서 인접한 도시의 정보가 주어집니다.
(i, j)가 0이면 인접X, 1이면 인접한 도시입니다.
1이 주어질때마다 union-find로 parent를 갱신해줍니다.
마지막으로 M개 도시의 parent가 모두 같으면 YES, 하나라도 다르면 NO입니다.
[Union-find]
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> travel;
int parent[201];
int N, M;
void init() {
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
int find(int v) {
if (parent[v] == v) return v;
return parent[v] = find(parent[v]);
}
void func() {
int x = find(travel[0]);
for (int i = 1; i < M; i++) {
int y = find(travel[i]);
if (x != y) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
void Union(int x, int y) {
if (x > y) swap(x, y);
int a = find(x);
int b = find(y);
parent[b] = a;
}
void input() {
int k;
cin >> N >> M;
init();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> k;
if (k) {
Union(i, j);
}
}
}
for (int i = 0; i < M; i++) {
cin >> k;
travel.push_back(k);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
그 다음은 dfs를 이용한 방법입니다.
위와 마찬가지로 0이면 인접X, 1이면 인접한 정점이므로 벡터에 넣어줍니다.
그 다음 M개의 도시 중 첫번째 도시를 루트로 dfs를 돌려줍니다. (이 때 방문체크를 한 것을 이용합니다.)
마지막으로 dfs로 순회하면서 M개의 도시를 모두 방문하였는지 체크해줍니다.
하나라도 방문을 하지 않았으면 연결이 안되어있다는 말이므로 NO를 출력해줍니다.
M개의 도시를 모두 방문하였으면 YES를 출력합니다.
[dfs]
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> graph[201], travel;
bool visit[201];
int N, M;
void func() {
for (int i = 0; i < M; i++) {
int x = travel[i];
if (visit[x]) continue;
cout << "NO\n";
return;
}
cout << "YES\n";
}
void dfs(int v) {
visit[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
if (visit[next]) continue;
dfs(next);
}
}
void input() {
int k;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> k;
if (k) graph[i].push_back(j);
}
}
for (int i = 0; i < M; i++) {
cin >> k;
travel.push_back(k);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
dfs(travel[0]);
func();
return 0;
}
|
cs |
'algorithm > Union-Find' 카테고리의 다른 글
| boj 20040 사이클 게임 (0) | 2021.06.27 |
|---|---|
| boj 1043 거짓말 (0) | 2021.04.05 |
| boj 10775 공항 (0) | 2021.03.17 |
| boj 4195 친구 네트워크 (0) | 2021.03.17 |
| boj 1717 집합의 표현 (0) | 2021.02.06 |