BOJ 1865 - 웜홀

BOJ 1865 - 웜홀

“벨만-포드 알고리즘”

BOJ 1865 - 웜홀

문제 링크



#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;

int N, M, W;
int dist[505];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int TC;
    cin >> TC;

    while (TC--) {
        cin >> N >> M >> W;
        vector<pair<int,int>> adj[505];
        for (int i = 0; i < M; i++) {
            int S,E,T; cin>>S>>E>>T;
            adj[S].push_back({E, T});
            adj[E].push_back({S, T});
        }
        for (int i = 0; i < W; i++) {
            int S,E,T; cin>>S>>E>>T;
            adj[S].push_back({E,-T});
        }
        bool nc = false;
        dist[1] = 0;
        // 모든 정점의 개수만큼
        for (int k = 0; k < N; k++) {
            // 모든 정점에 대하여
            for (int i = 1; i <= N; i++) {
                // 정점의 연결부에 대하여
                for (int j = 0; j < adj[i].size(); j++) {
                    int dst = adj[i][j].first;
                    int w = adj[i][j].second;
                    if (dist[dst] > dist[i] + w) {
                        dist[dst] = dist[i] + w;
                        if (k == N - 1)
                            nc = true ;
                    }
                }
            }
        }
        if (nc)
            cout << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}
  • 벨만-포드 알고리즘을 사용하여 그래프에 음의 사이클이 존재하는지를 찾아 결과값을 출력하는 문제이다. 구글 선생님이 수많은 자료를 던져줬지만 내 머리가 나빠서 제대로 이해할 수 있는 자료가 거의 없었다(dp이후로 이정도로 벽느껴진건처음;). 아래 사이트를 보고 공부했다. 이 문제는 벨만-포드 알고리즘을 살짝 비틀어서 구현해야 하는데, 아래 사이트에는 정석적인 벨만-포드 알고리즘에 대해서도 다루고 있기 때문에 공부하기가 한결 좋았다.

[BOJ] 백준 1865 - 웜홀

  • 지금까지 길찾기 알고리즘으로 다익스트라 / 플로이드-워셜 / 벨만-포드 알고리즘을 공부했는데, 그 중에서는 제일 어렵게 느껴졌던 것 같다. 사실 그래프의 가중치가 음수로 주어지는 경우가 많지 않다고 해서 대충 공부하고 넘어갈까 싶긴 했는데, 그래도 알아둬야 할 것 같아서 포스트를 작성한다.

  • 가장 중요한 점은 정점이 N개인 경우, N - 1의 순회를 통해 정점 1에 대해 모든 정점과의 거리를 계산할 수 있다는 점이다. 벨만-포드 알고리즘은 다익스트라 알고리즘처럼 그리디하게 그 상황에서 가장 짧은 노드로 찾아들어가는 것이 아니라, 정직하게 N-1번씩 순회하면서 하나하나 계산하기 때문에 다익스트라 알고리즘보다 시간 복잡도가 높지만, 음의 가중치를 감지해낼 수가 있다.

  • 음의 가중치를 가지고 있는 그래프를 감지한 , N - 1의 순회가 끝나 dist 배열이 완성시킨 후