[백준 1865] 웜홀

🔗 알고리즘 문제

문제를 꼼꼼히 읽지 않아서 몇번 틀렸던 문제이다. 앞으로 문제를 휙휙 넘기지 말고 찬찬히 읽어봐야겠다..

문제 분석

이 문제는 가중치가 양수인 무향간선과 가중치가 음수인 유향간선의 정보가 주어질 때 해당 그래프에서 음수 사이클이 일어나는지 체크하는 간단한 벨만 포드 문제이다.

발상 & 알고리즘 설계

이 문제에서는 음수 사이클이 일어나는지 아닌지만 체크하면 되기에 간단히 벨만 포드를 구현해주었는데, 자꾸 틀렸습니다.가 나왔다.

문제를 찬찬히 읽어보니 해당 문제에서는 시작 점이 어떤 점이라고 했지만, 그 어떤 점이 무조건 1은 아니라는 것을 깨달았다.

check[1] = 0;

for(int i = 0; i < n - 1; i++){
    for(int j = 0; j < edges.size(); j++){
        Edge e = edges[j];

        if(check[e.start] != MAX && check[e.end] > check[e.start] + e.val){
        	check[e.end] = check[e.start] + e.val;
    	}
	}
}

나는 대충 이런식으로 시작점을 1이라고 치고 벨만 포드를 구현하였는데, 이렇게 되면

1
2 0 1
2 2 1

Ans
-----
YES

해당 테스트케이스에서 시작점 1로 다시 돌아올 수 없기에 NO가 출력되게 된다.

어느 점에서든 음수 사이클을 체크할 수 있도록 INF비교를 하지 않고 벨만포드를 진행해주었다.

코드

#include<iostream>
#include<vector>

using namespace std;

#define MAX 2000000000

class Edge{
public:
    Edge(int start, int end, int val){
        this->start = start;
        this->end = end;
        this->val = val;
    }

public:
    int start;
    int end;
    int val;

};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;

    cin >> t;

    while(t--){
        int n;
        int m;
        int w;

        bool loop = false;

        vector<Edge> edges;
        int check[501] = {};

        cin >> n >> m >> w;

        for(int i = 1; i <= n; i++)
            check[i] = MAX;

        for(int i = 0; i < m; i++){
            int start;
            int end;
            int val;
            cin >> start >> end >> val;
            edges.emplace_back(start, end, val);
            edges.emplace_back(end, start, val);
        }

        for(int i = 0; i < w; i++){
            int start;
            int end;
            int val;
            cin >> start >> end >> val;
            edges.emplace_back(start, end, -val);
        }

        for(int i = 0; i < n - 1; i++){
            for(int j = 0; j < edges.size(); j++){
                Edge e = edges[j];

                if(check[e.end] > check[e.start] + e.val){
                    check[e.end] = check[e.start] + e.val;
                }
            }
        }

        for(int j = 0; j < edges.size(); j++){
            Edge e = edges[j];

            if(check[e.end] > check[e.start] + e.val){
                loop = true;
                break;
            }
        }

        cout << (loop ? "YES" : "NO") << "\n";
    }
}