알고리즘 풀이/수학
BOJ 11657 [타임머신]
갓우태
2021. 3. 19. 22:50
BOJ 11657 : www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
처음에 queue에 넣어서 bfs처럼 풀어보려고 시도했으나, cycle을 알아낼 마땅한 방법이 떠오르지 않아 재귀 형식으로 바꿨다.
key point는 재귀함수 내의 if문이다.
- 현재 재귀호출하면서 방문한 적 없는가?
- 현재 재귀 내에서 방문한 적이 없더라도, 이전에 방문했을 때 저장된 값(arr)보다 적은 시간이 걸리는가?
이 두가지를 따져가며 풀 수 있었다.
먼저 1을 방문한다. 1의 다음 도시는 2, 3인데 2부터 방문해본다.
방문한 적 없으니 2로 들어가되, 현재 도달한 시간이 저장된 값보다 작으므로 업데이트한다.
3도 방문한 적 없으니 방문체크 하고, 저장된 값보다 작으므로 업데이트한다.
현재 가지에서 1을 방문한 적이 있다. cycle을 찾았으니 이제 시간을 무한히 줄일 수 있는지가 관건이다.
현재 저장한 값보다 작으면 무한히 작아질 수 있다.
나아가다 보면 재귀에서 빠져나올 때 마다 방문체크를 풀어준다.
다시 줄기를 시작했을 때 저장된 시간을 계속 체크하며 업데이트 해준다.
|
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
|
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int arr[501];
bool visited[501];
struct City {
public:
int destination, distance;
};
vector<vector<City>> cities;
int result = 0;
void recursive(int current) {
for (City c : cities[current]) {
int next = c.destination;
int dist = c.distance;
if (!visited[next]) {
visited[next] = true;
if (arr[next] > arr[current] + dist) {
arr[next] = arr[current] + dist;
dfs(next);
}
visited[next] = false;
}
else {
if (arr[next] > arr[current] + dist) {
result = -1;
return;
}
}
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N, M;
cin >> N >> M;
cities.resize(N + 1);
fill_n(arr, N + 1, INT_MAX);
arr[1] = 0;
for (int busIdx = 0; busIdx < M; busIdx++) {
int A, B, C;
cin >> A >> B >> C;
City city;
city.destination = B;
city.distance = C;
cities[A].push_back(city);
}
visited[1] = true;
dfs(1);
if (result == -1) {
cout << result << "\n";
}
else {
for (int i = 2; i <= N; i++) {
if (arr[i] == INT_MAX) {
cout << "-1\n";
}
else {
cout << arr[i] << "\n";
}
}
}
return 0;
}
|
cs |
반응형