반응형

https://www.acmicpc.net/problem/1865

 

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보고 오시는 걸 추천드립니다!!

https://rudalsd.tistory.com/22

 

벨만 포드 알고리즘(Bellman-Ford Algorithm)

오늘 설명할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 벨만 포드 알고리즘이 dijkstra보다 시

rudalsd.tistory.com

 

이번 문제에서는 일반적인 최단거리를 구하는 문제들과는 다르게 단순히 음의 cycle이 있는지 없는지만 체크해주면 되는 문제입니다.

 

따라서 일반적인 벨만 포드 알고리즘과 달리 각 노드까지의 거리를 어떤 수로도 초기화시켜주어도 되고, 갱신이 된 적이 없는 노드들도 모두 돌아가면서 거리가 갱신되는지 체크해주면 됩니다.

 

마지막에 거리가 갱신이 된다면 음의 사이클이 존재한다는 뜻이므로 YES를 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
int N, M, W;
 
struct Node {
    int to;
    int dist;
};
 
int dist[501];
 
int main()
{
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N >> M >> W;
        vector<Node> list[501];
 
        memset(dist, -1, sizeof(dist));
 
        for (int i = 0; i < M; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,T });
            list[E].push_back({ S,T });
        }
 
        for (int i = 0; i < W; i++) {
            int S, E, T;
            scanf("%d %d %d", &S, &E, &T);
            list[S].push_back({ E,-T });
        }
 
        int flag = 0;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 0; k < list[j].size(); k++) {
                    int next = list[j][k].to;
                    int nextDist = list[j][k].dist;
                    if (dist[next] > nextDist + dist[j]) {    //N번째에도 거리가 줄어들었다면 음의 cycle이 있다는 뜻이므로
                        dist[next] = nextDist + dist[j];
                        if (i == N) {
                            flag = 1;
                        }
                    }
                }
            }
        }
 
        if (flag == 1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11
[ 백준 ] 1238번 - 파티 (C++)  (0) 2022.06.09
[ 백준 ] 12865번 - 평범한 배낭 (C++)  (0) 2022.06.08
[ 백준 ] 9663번 - N-Queen (C++)  (0) 2022.06.07
반응형

오늘 설명할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 벨만 포드 알고리즘이 dijkstra보다 시간은 더 오래 걸리지만 특정 상황에서 dijkstra는 구하지 못하는 최단거리를 구할 수 있기 때문에 사용합니다.

 

dijkstra는 음의 간선이 있을 때 최단거리를 구할 수 없지만 벨만 포드 알고리즘은 음의 간선이 있어도 최단거리를 구할 수 있습니다.

 

​벨만 포드 알고리즘이 오래 걸리는 이유는 dijkstra는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 비용을 갱신하였지만, 벨만 포드 알고리즘은 음의 간선 때문에 모든 경우의 수를 다 탐색해야 하기 때문입니다.

 

[ 동작 원리 ]

  1. 시작 정점을 선택합니다.
  2. 모든 정점들을 N-1번 탐색하면서, 정점에 이어진 간선들을 모두 체크합니다. 해당 정점의 값이 INF가 아니라면 간선들을 체크하여 다음 노드로 가는 거리가 현재보다 더 짧다면 거리를 갱신해줍니다.
  3. 마지막으로 N번째 탐색 때 거리가 갱신된다면 이는 음의 cycle을 가진 그래프입니다.

 

2번 과정에서 N-1번 탐색하는 이유는 N번 노드까지 가는데 최단 거리는 최대 N-1개의 정점을 통과하기 때문입니다.

 

만약 3번 과정에서 거리가 갱신된다면 음의 cycle이 존재해서 최단거리가 계속 갱신되는 상황이므로 이 그래프는 최단거리를 구할 수 없는 그래프가 됩니다.

 

벨만 포드 알고리즘의 동작 과정을 그림으로 이해봅시다.

 

 

시작 정점은 1번 노드이고, 각 정점들까지의 최단 거리를 구해봅시다.

 

1번 노드를 제외한 모든 노드들은 INF로 초기화시켜서 갱신된 적이 있는지 없는지 체크합니다.

 

 

먼저 1번 노드에서부터 연결된 간선들을 모두 체크해줍니다. 간선들은 2번, 3번, 4번 노드들과 연결이 되어있고, 각각의 노드로 가는데 이동거리는 각각 7, 5, 3입니다. 따라서 표를 갱신해주면 다음과 같은 결과를 얻을 수 있습니다.

 

 

이제는 5번 노드를 제외한 모든 노드들이 한 번씩 갱신되었기 때문에 1번부터 4번 노드까지 연결되어 있는 모든 간선들을 체크해 최단거리를 갱신해줍니다.

 

예를 들어 4번 노드에서 2번 노드로 가는 거리(3+3)가 현재 2번 노드까지의 거리(7) 보다 더 짧으므로 2번 노드까지의 이동거리를 갱신해줍니다. 다른 노드들도 마찬가지 방법을 이용해 N-1번 거리를 갱신해주면 다음과 같은 결과를 얻을 수 있습니다.

 

보통의 그래프라면 위의 표의 상태가 각 노드까지의 최단거리를 표현한 것입니다. 하지만 이 그래프가 음의 cycle을 가지고 있는지 없는지 체크하기 위해 마지막 N번 째 탐색을 더 해봐야 합니다.

 

마지막 탐색을 해본 결과 다음과 같은 결과를 얻을 수 있습니다.

 

 

1번 노드를 제외한 모든 노드들이 갱신되었습니다. 그 이유는 5-3-4의 사이클에서 항상 거리가 -1(2+3-6)만큼 감소하면서 갱신이 되기 때문입니다. 따라서 위의 그래프는 모든 노드들에 대해서 최단거리를 구할 수 없는 그래프입니다.

 

벨만 포드 알고리즘은 정점의 수만큼 모든 간선을 탐색하기 때문에 O(NE)의 시간 복잡도를 가집니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <vector>
 
#define INF 2e8
 
using namespace std;
 
struct Node {
    int node;
    int cost;
};
 
long long dist[501];
vector<Node> list[501];
 
int main()
{
    int N, M;
    cin >> N >> M;
    
    for (int i = 2; i <= N; i++) {
        dist[i] = INF;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        list[A].push_back({ B,C });
    }
 
    int lastUpdate = 0;
 
    for (int n = 0; n < N; n++) {
        lastUpdate = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] == INF) continue;
            for (int j = 0; j < list[i].size(); j++) {
                if (dist[list[i][j].node] > dist[i] + list[i][j].cost) {
                    dist[list[i][j].node] = dist[i] + list[i][j].cost;
                    lastUpdate = 1;
                }
            }
        }
        if (lastUpdate == 0) break;
    }
 
    if (lastUpdate == 1) {
        cout << -1;
    }
    else {
        for (int i = 2; i <= N; i++)
        {
            if (dist[i] != INF) {
                cout << dist[i] << endl;
            }
            else {
                cout << -1 << endl;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 오일러 피 함수(Euler's phi function)  (0) 2022.07.09
[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)  (0) 2022.06.30
[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)  (0) 2022.06.29
[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)  (0) 2022.06.21
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)  (0) 2022.06.11

+ Recent posts

티스토리툴바