출처 : https://www.acmicpc.net/problem/11657
타임머신 성공 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 4829 | 1906 | 1143 | 38.381% |
문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
출력
첫째 줄에는 2번 도시까지 가는 가장 빠른 시간, ..., N-1번째 줄에는 N번 도시까지 가는 가장 빠른 시간을 출력한다. 어떤 도시로 가는 가장 빠른 시간이 없는 경우에는 -1을 출력한다.
만약, 시작점에서 도달 가능한 타임머신으로 되어있는 사이클이 존재해 1번 도시에서 나머지 도시로 가는 가장 빠른 시간이 존재하지 않는 경우에는 -1을 출력한다.
예제 입력
3 4 1 2 4 1 3 3 2 3 -1 3 1 -2
예제 출력
4 3
예제 입력 2
3 4 1 2 4 1 3 3 2 3 -4 3 1 -2
예제 출력 2
-1
예제 입력 3
3 2 1 2 4 1 2 3
예제 출력 3
3 -1
힌트
>> 문제 해결 방법
이 문제는 벨만-포드 알고리즘으로 해결한다.
벨만-포드 알고리즘의 설명은 아래의 링크를 따라가면 자세히 볼 수 있다.
http://algo-revolution.blogspot.kr/2016/05/bellman-ford-algorithm.html
http://www.crocus.co.kr/534
https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
https://www.acmicpc.net/board/view/21965 (백준 알고리즘 아이디 필요)
내가 이 문제를 풀면서 실수한 것은, 각 노드를 돌 때마다 모든 엣지들을 조사해야 하는데 그 점을 간과한 것이다.
나는 각 노드를 돌 때마다, 각 노드에 연결된 엣지들만 조사했는데 그게 아니라 모든 엣지에 대하여 지속적으로 갱신을 수행해야 한다.
시간 복잡도는 모든 V 에 대하여, E 번 수행하기 때문에 O(|V|*|E|) 이다.
>> 소스코드
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 <queue> #define INF 987654321 #define MAX_NODE 501 using namespace std; typedef struct EDGE { int dest; int val; }; // 0번 인덱스는 버린다. vector<EDGE> edge_vec[MAX_NODE]; int value_arr[MAX_NODE] = { 0 }; int N, M; int bellman_ford(int excute_num) { int isChanged = 0; // 벨만 포드 알고리즘을 수행한다. // 모든 VERTEX 에서 연결된 EDGE 를 확인해야 한다. // i가 시작점 edge_vec[i][k].dest 가 도착점 // 각 노드마다 한 번씩 수행한다. for (int t = 1; t <= N; t++) { // 각 노드마다 모든 엣지에 대하여 for (int i = 1; i <= N; i++) { for (int k = 0; k < edge_vec[i].size(); k++) { // 현재 목적지에 가는 노드의 가중치와, 출발 노드에서 목적지 까지 가는 노드의 가중치를 각각 구한다. int new_val = (value_arr[i] + edge_vec[i][k].val); int before_val = (value_arr[edge_vec[i][k].dest]); // 노드 값이 지금 값 보다 크면 갱신한다. if ((value_arr[i] != INF) && (new_val < before_val)) { isChanged = 1; // 만약 2번째 수행 후라면 바로 함수를 종료한다. if (isChanged * excute_num) return isChanged; value_arr[edge_vec[i][k].dest] = new_val; } } } } return isChanged; } int main() { cin >> N >> M; // EDGE 입력받기 int from, to, val; for (int i = 0; i < M; i++) { scanf("%d %d %d", &from, &to, &val ); edge_vec[from].push_back(EDGE{to, val}); } // 초기 도달 가능한 시간을 INF 으로 초기화 for (int i = 2; i <= N; i++) value_arr[i] = INF; // 벨만 포드 알고리즘 수행 bellman_ford(0); // 두 번째 수행해서 만약 변경되는 값이 있으면, 함수에서 1이 리턴된다. if (bellman_ford(1) == 1) { cout << -1; } // 함수 리턴 값이 0이면 변한 값이 없기 때문에, 바로 값을 출력한다. else { for (int i = 2; i <= N; i++) printf("%d\n", (value_arr[i]!=INF ? value_arr[i] : -1) ); } return 0; } | cs |