baekjoon 1865:웜홀

baekjoon 1865 웜홀

1865번 웜홀

접근

negCycle을 찾아야하는 문제이다. negCycle을 찾는 알고리즘은 벨만포드 알고리즘이 있다.
negCycle은 무한정 reweighting되는 문제가 있다. 그래서 벨만포드는 v-1번 돌면 모든 최단 거리를
찾아야 정상이다. 그런데 1번 더 돌았을 때 reweighting이 되면 negCycle이 있다는 증거이다.

그런데 원래는 벨만포드가 one source shortest path 알고리즘이라는 것이다.
그것 자체는 문제가 되지 않지만 이번 문제에서는 연결 그래프가 아닐 수 있다는 문제가 있다.
어떤 vertex를 시작점으로 잡느냐에 따라 갈 수 없는 vertex가 생긴다.
그래서 처음엔 각 component마다 벨만포드를 돌려고 했다. 그런데 이렇게 하면 최악의 경우에는 모든 vertex마다
벨만포드를 돌게 생겼다. 무조건 시간초과가 나게 된다.
그래서 모든 점에 동시에 reweighting을 하는 방법을 사용했다.
dist[next] != MAXN을 지워서 모든 곳을 다 reweighting 할거다.
이렇게 하면 최단거리는 못 구하지만 negCycle은 찾을 수 있다.

코드

실패코드

#include <iostream>
#include <vector>
#include <array>
using namespace std;
const int MAXN = 1e7;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int tc; cin >> tc;
  for(int i = 0; i < tc; i++){
    int n, m, w; cin >> n >> m >> w;
    array<vector<pair<int, int>>, 500> adj;
    for(int j = 0; j < m; j++){
      int s, e, t; cin >> s >> e >> t;
      adj[s-1].push_back({e-1, t});
      adj[e-1].push_back({s-1, t});
    }
    for(int j = 0; j < w; j++){
      int s, e, t; cin >> s >> e >> t;
      adj[s-1].push_back({e-1, t*(-1)});
    }
    //graph 만듦
    array<bool, 500> visited;
    fill(visited.begin(), visited.begin() + n, false);
    array<int, 500> dist;
    fill(dist.begin(), dist.begin() + n, MAXN);
    bool negCycle = false;
    for(int j = 0; j < n; j++){
      if(!visited[j]){ //각 컴포넌트 기준으로 bellman-ford 돌리기로 했다
        dist[j] = 0;
        visited[j] = true;
        for(int k = 0; k < n; k++){
          for(int p = 0; p < n; p++){
            for(auto& q: adj[p]){
              int next = q.first, d = q.second;
              if(dist[next] != MAXN && dist[next] > dist[p]+d){
                dist[next] = dist[p]+d;
                visited[next] = true;
                if(k == n-1){
                  negCycle = true;
                }
              }
            }
          }
        }
        if(negCycle){
          break;
        }
      }
    }
    if(negCycle){
      cout << "YES\n";
    }
    else{
      cout << "NO\n";
    }
  }
  return 0;
}

성공코드

#include <iostream>
#include <vector>
#include <array>
using namespace std;
const int MAXN = 1e7;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int tc; cin >> tc;
  for(int i = 0; i < tc; i++){
    int n, m, w; cin >> n >> m >> w;
    array<vector<pair<int, int>>, 500> adj;
    for(int j = 0; j < m; j++){
      int s, e, t; cin >> s >> e >> t;
      adj[s-1].push_back({e-1, t});
      adj[e-1].push_back({s-1, t});
    }
    for(int j = 0; j < w; j++){
      int s, e, t; cin >> s >> e >> t;
      adj[s-1].push_back({e-1, t*(-1)});
    }
    //graph 만듦
    array<bool, 500> visited;
    fill(visited.begin(), visited.begin() + n, false);
    array<int, 500> dist;
    fill(dist.begin(), dist.begin() + n, 3);
    bool negCycle = false;
    for(int k = 0; k < n; k++){
      for(int p = 0; p < n; p++){
        for(auto& q: adj[p]){
          int next = q.first, d = q.second;
          if(dist[next] > dist[p]+d){
            dist[next] = dist[p]+d;
            visited[next] = true;
            if(k == n-1){
              negCycle = true;
            }
          }
        }
      }
    }
    if(negCycle){
      cout << "YES\n";
    }
    else{
      cout << "NO\n";
    }
  }
  return 0;
}
//https://www.acmicpc.net/board/view/72995

배운 점

벨만포드 구현법도 배웠고 응용법도 배웠다.