https://www.acmicpc.net/problem/1976
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
find 연산의 작동 원리
1. parent 배열에 index 값과 value 값이 동일한지 확인
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동
3. 재귀로 반복 return parent[a] = find(parent[a]);
3. 대표 노드에 도달하면 재귀 함수를 빠져나오면서
거치는 모든 노드값을 대표 노드값으로 변경
이 문제는 유니온 파인드 문제다.
인접 행렬을 for문으로 돌면서 1이면 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> parent;
int find(int a)
{
if (a == parent[a])
return a;
else
// 재귀 함수로 구현
// 재귀를 탈출하면서 parent의 값이 바뀐다.
return parent[a] = find(parent[a]);
}
void unionfunc(int a, int b)
{
a = find(a);
b = find(b);
if (a != b)
parent[b] = a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
int map[201][201];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
}
}
int route[1001];
for (int i = 1; i <= m; i++)
{
cin >> route[i];
}
parent.resize(n + 1);
// 대표 노프들 자기 자신으로 초기화
for (int i = 1; i <= n; i++)
{
parent[i] = i;
}
// 인접 행렬 탐색
// 도시가 연결되어 있으면 유니온 실행
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (map[i][j] == 1)
{
unionfunc(i, j);
}
}
}
// 여행 계획 도시가 하나의 대표 도시로 연결 되나 확인
// 여향 경로의 도시의 값이 index와 모두 같아야 한다.
int index = find(route[1]);
bool connect = true;
for (int i = 2; i <= m; i++)
{
if (index != find(route[i]))
{
cout << "NO" << '\n';
connect = false;
break;
}
}
if (connect)
{
cout << "YES" << '\n';
}
return 0;
}
|
cs |