알고리즘
BFS
입력으로 들어온, 알려진 전후관계로 그래프를 만듦.
- 체크를 해야하는 원소 두개가 들어오면,
- 먼저 첫번째 거에서 bfs를 시작하여 두번째거가 나오면 첫번째가 앞에 있는 것이므로 -1를 출력
- 찾지못하면, 두번째에서 첫번째를 BFS로 찾음. 찾으면 1을 출력.
- 찾지못하면, 0 을 출력
- 시간 복잡도 : O(NM)
- 사건의 개수 - N, 찾아야하는 선후관계 - M
- N은 최대 400, M은 최대 50000임. 대략 2천만번의 연산 필요.
- 하지만 첫번째에서 두번째/ 두번째에서 첫번째로 총 2번 검사하여야하고, 매 bfs 마다 400개 사건에 대한 visit 배열을 초기화하여야함.
- 따라서 대략 8천만번이라고 보는 것이 합당함.
플로이드 워셜
- 플로이드 워셜 알고리즘을 사용하여, 한 사건에서 다른 사건으로 가는 최소 경로를 찾음. -> map[][]에 저장
- 체크를 해야하는 원소 a, b가 들어오면,
- map[a][b]가 있으면,-1 출력
- map[b][a] 가 있으면, 1 출력
- 둘다 없으면 0 출력
- 시간 복잡도 : N^3 + M*O(1) = O(N^3 + M)
- N 은 최대 400개, M은 최대 50000이므로, 대략 6천4백만번의 연산 필요
어느게 빠를까?
- 플로이드 워셜 방법이 압도적으로 빨랐다.
- BFS - 1000ms, 플로이드 워셜 - 80ms
- 연산 횟수는 두 방법에서 크게 차이나지 않았으나, bfs 방법에선 그래프를 만드는데 vector를 사용하였고, bfs를 구현하는데 queue 를 사용하였다.
- 하지만 플로이드 워셜 방법은 다른 라이브러리의 도움 없이 구현할 수 있었다.
- 이러한 차이로 플로이드 워셜 방법이 압도적으로 빨랐다고 생각된다.
코드
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
#include <iostream>
#define INF 1000000000
using namespace std;
int n, k, s, map[401][401];
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0; i <= 400; i++) {
for (int j = 0; j <= 400; j++) {
if(i != j)
map[i][j] = INF;
}
}
int a, b;
cin >> n >> k;
for (int i = 0; i < k; i++) {
cin >> a >> b;
map[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
map[j][k] = min(map[j][k], map[j][i] + map[i][k]);
}
}
}
cin >> s;
for (int i = 0; i < s; i++) {
cin >> a >> b;
if (map[a][b] != INF)
cout << -1 << "\n";
else if (map[b][a] != INF)
cout << 1 << "\n";
else
cout << 0 << "\n";
}
}