[백준/Baekjoon] 1865 웜홀 C++ :: Bellman-Ford

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

1865번: 웜홀

---

1. Logic

- 해당 문제에서 시간이 거꾸로 가는 경로인 웜홀이 존재한다고 하였다. 이건 음수 간선을 나타내는 말이기 때문에 그래프 최단거리 알고리즘 중에서 음수가중치가 있을 때 사용할 수 있는 방법인 벨만-포드 알고리즘을 사용해서 풀이할 수 있다.

 

원래 벨만 포드 알고리즘은 V(노드의 갯수)-1만큼 순회하며 모든 간선을 확인하며 최단거리를 구하는 방법이다. 

이 문제에서는 음수싸이클이 있는지를 확인해야하기 때문에 최악의 경우  V-1만큼 순회를 했을때 모든 정점까지 최단 거리가 구해지고 한번 더 돌았을 때 최단거리가 갱신되는 현상이 있다면 음수싸이클이 존재하는 것임으로 정답을 출력한다.

 

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m, w;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> adj[501];

void bellman(int start, int target) {
    //모든 정점까지의 최단거리 상한
    vector<int> upper(501, INF);
    bool update = false;
    upper[start] = 0;

    for (int iter = 0; iter < n; ++iter) {
        update = false;
        for(int here = 1; here <= n; ++here) {
            for(int i = 0; i < adj[here].size(); i++) {
                int cost = adj[here][i].first;
                int there = adj[here][i].second;
                if(upper[there] > upper[here] + cost) {
                    upper[there] = upper[here] + cost;
                    update = true;
                }
            }
        }
        if(!update) {
            cout << "NO" <<"\n";
            break;
        }
    }
    if(update)
        cout << "YES" << "\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tc;
    cin >> tc;

    while (tc--) {
        cin >> n >> m >> w;

        for (int i = 0; i <= n; i++) {
            adj[i].clear();
        }

        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({t, e});
            adj[e].push_back({t, s});
        }

        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({-t, e});
        }

        bellman(1, n);
    }
}

 

---

 

3. Feedback

알고리즘 공부를 박치기 식으로해서 어떻게 돌아가는지 이해도가 부족했던 것 같다. 앞으로 알고리즘을 조금더 딥하게 공부해야겠다.

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90