백준 1865번 [웜홀](C++) -yes6686- 티스토리

백준 문제 풀이: 1865 [웜홀]

---

문제 링크: https://www.acmicpc.net/problem/1865

문제 설명:

여러 개의 마을과 마을을 잇는 도로 및 웜홀이 있을 때, 웜홀을 이용해 시간이 음수인 사이클을 형성할 수 있는지를 판별하는 문제입니다.

입력:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 5)
• 각 테스트 케이스의 첫 줄에는 마을의 수 n, 도로의 수 m, 웜홀의 수 w가 주어집니다. (1 ≤ n ≤ 500, 1 ≤ m ≤ 2,500, 1 ≤ w ≤ 200)
• 다음 m개의 줄에는 두 마을을 잇는 도로 정보 s e t가 주어지며, 이는 s에서 e로 가는 시간이 t임을 나타냅니다.
• 다음 w개의 줄에는 웜홀 정보 s e t가 주어지며, 이는 s에서 e로 가는 시간이 -t임을 나타냅니다.

출력:

• 각 테스트 케이스마다 시간이 음수인 사이클이 존재하면 "YES", 존재하지 않으면 "NO"를 출력합니다.

예시:

입력:
1
3 3 1
1 2 2
2 3 2
3 1 2
1 3 3

출력:
YES

---

문제 해결 코드

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

const int INF = 1e9;

bool bellmanFord(int n, vector<tuple<int, int, int>>& edges) {
    vector<int> dist(n + 1, INF);
    dist[1] = 0;

    for (int i = 1; i < n; i++) {
        for (auto &[u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    for (auto &[u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return true; // 음수 사이클 존재
        }
    }

    return false; // 음수 사이클 없음
}

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

    int T;
    cin >> T;

    while (T--) {
        int n, m, w;
        cin >> n >> m >> w;

        vector<tuple<int, int, int>> edges;

        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            edges.emplace_back(s, e, t);
            edges.emplace_back(e, s, t); // 양방향 도로
        }

        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            edges.emplace_back(s, e, -t); // 웜홀은 단방향
        }

        if (bellmanFord(n, edges)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

---

코드 설명

이 코드는 벨만-포드 알고리즘을 사용하여 음수 사이클의 존재 여부를 확인합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 벨만-포드 알고리즘:
  • n-1번 반복하며 모든 간선을 완화합니다.
  • n번째 반복에서 간선이 완화된다면, 음수 사이클이 존재한다고 판별합니다.
• 구현 세부사항:
  • dist[u]: 시작점에서 정점 u까지의 최단 거리를 저장합니다.
  • edges: 모든 간선을 저장하는 벡터입니다.
• 시간 복잡도:
  • 간선 수를 E, 정점 수를 n라고 할 때, 시간 복잡도는 O(n × E)입니다.

---

예제

다음은 임의로 생성한 테스트 예제입니다:

입력:
1
4 4 1
1 2 3
2 3 4
3 4 5
4 1 6
1 4 8

출력:
NO

이 예제에서는 음수 사이클이 존재하지 않으므로 "NO"가 출력됩니다.

---

결과

코드는 음수 사이클의 존재 여부를 정확히 판별하며, 테스트 케이스 크기에 따라 효율적으로 작동합니다. 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!