[백준 1865] 웜홀 (C#, C++) - soo:bak

문제 링크

1865번 - 웜홀

설명

도로와 웜홀이 있는 그래프가 주어지는 상황에서, 테스트케이스 개수 TC, 각 테스트케이스마다 지점의 개수 N (1 ≤ N ≤ 500), 도로의 개수 M (1 ≤ M ≤ 2,500), 웜홀의 개수 W (1 ≤ W ≤ 200), 그리고 각 도로와 웜홀의 정보가 주어질 때, 출발 지점으로 돌아왔을 때 시간이 되돌아가 있는 경우가 존재하는지 판별하는 문제입니다.

도로는 양방향이며 이동하는 데 양수 시간이 걸립니다. 웜홀은 단방향이며 지나가면 시간이 거꾸로 흐릅니다(음수 가중치). 시간이 되돌아가려면 그래프에 음수 사이클이 존재해야 합니다.

접근법

벨만-포드(Bellman-Ford) 알고리듬을 사용하여 음수 사이클의 존재 여부를 판별합니다.

모든 정점을 확인하기 위해 슈퍼 소스(가상의 시작점 0)를 추가하고, 슈퍼 소스에서 모든 정점으로 가중치 0인 간선을 연결합니다. 도로는 양방향이므로 양쪽 방향 간선을 모두 추가하고, 웜홀은 단방향이므로 음수 가중치 간선으로 추가합니다.

N번 반복하여 모든 간선을 확인하고 거리를 갱신한 후, 한 번 더 모든 간선을 확인합니다. 이때 거리가 갱신되면 음수 사이클이 존재하므로 YES를 출력하고, 갱신되지 않으면 NO를 출력합니다. 반복 과정에서 거리 갱신이 없으면 조기 종료합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var tc = int.Parse(Console.ReadLine()!);
      
      while (tc-- > 0) {
        var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var n = input[0];
        var m = input[1];
        var w = input[2];

        var edges = new List<(int from, int to, int time)>(2 * m + w + n);

        for (var i = 0; i < m; i++) {
          var road = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
          var start = road[0];
          var end = road[1];
          var time = road[2];
          edges.Add((start, end, time));
          edges.Add((end, start, time));
        }

        for (var i = 0; i < w; i++) {
          var wormhole = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
          var start = wormhole[0];
          var end = wormhole[1];
          var time = wormhole[2];
          edges.Add((start, end, -time));
        }

        for (var i = 1; i <= n; i++)
          edges.Add((0, i, 0));

        var dist = new int[n + 1];
        Array.Fill(dist, 0);
        var hasNegativeCycle = false;

        for (var iteration = 0; iteration <= n; iteration++) {
          var updated = false;
          
          foreach (var edge in edges) {
            var (from, to, time) = edge;
            if (dist[to] > dist[from] + time) {
              dist[to] = dist[from] + time;
              updated = true;
              
              if (iteration == n) {
                hasNegativeCycle = true;
                break;
              }
            }
          }
          
          if (!updated) break;
        }

        Console.WriteLine(hasNegativeCycle ? "YES" : "NO");
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int from, to, time;
};

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

  int tc; cin >> tc;
  
  while (tc--) {
    int n, m, w; cin >> n >> m >> w;
    vector<Edge> edges;
    edges.reserve(2 * m + w + n);

    for (int i = 0; i < m; i++) {
      int start, end, time;
      cin >> start >> end >> time;
      edges.push_back({start, end, time});
      edges.push_back({end, start, time});
    }
    
    for (int i = 0; i < w; i++) {
      int start, end, time;
      cin >> start >> end >> time;
      edges.push_back({start, end, -time});
    }
    
    for (int i = 1; i <= n; i++)
      edges.push_back({0, i, 0});

    vector<int> dist(n + 1, 0);
    bool hasNegativeCycle = false;

    for (int iteration = 0; iteration <= n; iteration++) {
      bool updated = false;
      
      for (const auto& edge : edges) {
        if (dist[edge.to] > dist[edge.from] + edge.time) {
          dist[edge.to] = dist[edge.from] + edge.time;
          updated = true;
          
          if (iteration == n) {
            hasNegativeCycle = true;
            break;
          }
        }
      }
      
      if (!updated) break;
    }

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

  return 0;
}