[백준] 1865번 - 웜홀 (C++)

Dingool95·2021년 12월 27일
0
post-custom-banner

포스팅 목적

벨만-포드 알고리즘에 대해서 외워서 풀어서 된통 당했다. 이 문제도 코드 한 줄 때문에 계속해서 틀려버렸다. 벨만-포드 알고리즘을 간선 리스트를 활용해서 풀었는데, 코드가 간결하고 좋아서 남겨두고자 하는 목적도 있다. 음의 사이클 판별하는 데 모범적인 코드이다.


예외적인 조건 하나

벨만-포드 알고리즘은 특정 정점으로부터 다른 모든 정점으로의 최단 거리를 구할 수 있다. 이 문제는 잘 읽어보면 출발점이 특정되어 있지 않다. 문제를 풀기 위해서 각 정점을 출발점으로 하여, 하나씩 사이클의 유무를 확인해보면 된다. 그런데 n <= 500이므로 절대 올바른 풀이가 아님을 짐작할 수 있다.

그럼 대체 어떻게?
이 문제는 최단 거리 따위는 관심없고, 음의 사이클의 존재 유무만 파악하면 된다. 풀이한 코드는 임의로 1번 정점을 출발점으로 잡았다.

일반적인 벨만-포드 알고리즘처럼 모든 거리를 INF로 초기화하고 dist[s] != INF 라는 조건을 넣어버리면, 1번 정점에 연결된 간선이 전혀 없을 경우에 다른 정점들은 relax되지 않는다. 다른 정점들의 거리값은 모두 INF로 유지되고, 음의 사이클이 존재하더라도 위 조건 때문에 알 수 없게 된다.

if (dist[s] != INF && dist[e] > dist[s] + t)	X

if (dist[e] > dist[s] + t)			o

아래 링크에 더 자세히 설명되어 있다.


코드

#include <iostream>
#include <vector>
using namespace std;

#define INF 5000000

int tc, n, m, w;
bool ncycle;

int dist[501];

class Edge {
public:
    int s, e, t;

    Edge(int a, int b, int c) {
        this->s = a;
        this->e = b;
        this->t = c;
    }
};
vector<Edge> Ed;

bool bellmanFord()
{
    dist[1] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < Ed.size(); ++j) {
            int s = Ed[j].s;
            int e = Ed[j].e;
            int t = Ed[j].t;
            
            if (dist[e] > dist[s] + t) { <-----------------------
                dist[e] = dist[s] + t;
                if (i == n) return true;
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> tc;
    for (int k = 1; k <= tc; ++k) {
        Ed.clear();
        for (int i = 1; i <= n; ++i) dist[i] = INF;

        cin >> n >> m >> w;
        for (int i = 1; i <= m; ++i) {
            int a, b, c; cin >> a >> b >> c;
            Ed.push_back(Edge(a, b, c));
            Ed.push_back(Edge(b, a, c));
        }
        for (int i = 1; i <= w; ++i) {
            int a, b, c; cin >> a >> b >> c;
            Ed.push_back(Edge(a, b, -c));
        }
        
        ncycle = bellmanFord();
        if (ncycle) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
profile
내 맘대로 요점정리
post-custom-banner

0개의 댓글