문제링크 : https://www.acmicpc.net/problem/1976
맨 처음 이 문제를 보았을 때 Brute Force로 경로를 찾는 방법밖에 없다고 생각했습니다. 하지만 그렇게 하게 되면 불필요한 연산을 하게 됩니다.
불필요한 연산이라 함은, 길의 첫번째에서 출발하여 길의 마지막번째에 도착하는 루트를 찾았다 하더라도 주인공인 '동혁'이가 원하는 길이 아닌경우 틀린 답이기 때문에 결국 길을 다른방법으로 다시 찾아야 되는 번거로움을 의미합니다.
따라서 저는 이 방법이 아닌 'Union Find' 방법을 사용했습니다.
Union Find를 사용하게 되면, 옛날 로마시대 도로망처럼, 모든길은 로마로 통한다 라는 말 처럼 현재노드와 바로 다음 노드의 부모노드만 같다면 어떻게 가든지 이어져는 있다라는 것을 의미 하므로 조금 더 편하게 path의 '존재'를 알게 될 것이기 때문 입니다.
소스코드 :
맨 처음 이 문제를 보았을 때 Brute Force로 경로를 찾는 방법밖에 없다고 생각했습니다. 하지만 그렇게 하게 되면 불필요한 연산을 하게 됩니다.
불필요한 연산이라 함은, 길의 첫번째에서 출발하여 길의 마지막번째에 도착하는 루트를 찾았다 하더라도 주인공인 '동혁'이가 원하는 길이 아닌경우 틀린 답이기 때문에 결국 길을 다른방법으로 다시 찾아야 되는 번거로움을 의미합니다.
따라서 저는 이 방법이 아닌 'Union Find' 방법을 사용했습니다.
Union Find를 사용하게 되면, 옛날 로마시대 도로망처럼, 모든길은 로마로 통한다 라는 말 처럼 현재노드와 바로 다음 노드의 부모노드만 같다면 어떻게 가든지 이어져는 있다라는 것을 의미 하므로 조금 더 편하게 path의 '존재'를 알게 될 것이기 때문 입니다.
소스코드 :
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
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
int root[201];
int n, m;
int Find(int x) {
if (root[x] == x) {
return x;
}
else {
return root[x] = Find(root[x]);
}
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
root[x] = y;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
for (int i = 1; i < 201; i++) {
root[i] = i;
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int tmp;
cin >> tmp;
if (tmp == 1) {
Union(i, j);
}
}
}
int a;
cin >> a;
int b = Find(a);
bool flag = false;
for (int i = 1; i < m; i++) {
cin >> a;
if (b != Find(a)) {
flag = true;
break;
}
}
if (flag) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
| cs |
댓글
댓글 쓰기