[백준] 11657번 C/C++ 풀이 _ 타임머신

[백준] 11657번 C/C++ 풀이 _ 타임머신
카테고리 Algorithm
제목 [백준] 11657번 C/C++ 풀이 _ 타임머신
작성시간 2018-03-04 01:10:53 +0900
조회수 430

출처 : https://www.acmicpc.net/problem/11657 

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB48291906114338.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






▼댓글▼

▼추천 게시물▼