[백준BOJ] 1219 오만식의 고민

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

1219번: 오민식의 고민

---

이 문제를 해결하는데 많은 시간이 걸렸고, 질문 게시판에서 힌트를 얻은 뒤에 풀 수 있었습니다.

왜 오래걸렸고, 유의해야될 점이나, 어떤식으로 풀어야되는지 포스팅 해보도록 하겠습니다.

아마 이문제를 풀기전에 https://www.acmicpc.net/problem/11657(타임머신), https://www.acmicpc.net/problem/1865(웜홀) 문제를 푸셨을텐데 단지, 코드를 외워서 풀었다면 저처럼 이문제에서 많은 어려움을 느끼셨을 것 같습니다. "오민식의 고민"문제에서 쉽게 해결하신분들은 아마 벨만포드 알고리즘의 작동원리를 잘 알고계셔서 풀었다고 생각이 됩니다. 

case : gg

DFS나 BFS를 통해 S노드에서 E노드를 방문할 수 없다면 그냥 gg를 출력하고 끝내면 됩니다.

 

void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

    DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

case : Gee

위의 언급한 타임머신, 웜홀 문제처럼 단지 cycle이 있는지 없는지를 통해 Gee를 출력하였다면 틀린 코드가 됩니다.

밑의 코드가 바로 그러한 코드입니다. 왜 이 코드가 틀렸는지 알아보도록 하겠습니다.

 

     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!
     bool cycle = false;
     dist[S] = earn[S];
     for (int i = 1; i <= N ; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] != LLONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         if (i == N)  dist[next] = LLONG_MAX;
                    }
               }
          }
     }
     if (cycle) cout << "Gee\n";
     else cout << dist[E] << "\n";
     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!

밑의 케이스를 보면

만약 1번노드와 2번노드사이에 사이클이생겨 돈을 무한으로 벌 수 있다면

위의 잘못된 코드에서는 "Gee"를 출력할 것입니다. 하지만 사실 1에서 3으로 가는 경우가 끝이죠.

또다른 예시를 보겠습니다.

위의 사진의 경우는 사이클이 있고 해당 사이클에서 무제한으로 돈을 벌어서 3(E)번 노드에 방문할 수 있습니다.

그렇다면 첫번째 예시의 잘못된 경우를 어떻게 처리 할 수 있을까요?

사이클이 생기는 경우 해당 사이클이 생기는 노드에서 E번노드를 갈 수있는지 없는지 체크 하면 됩니다.

 

<방법 1>

1.  V-1번 반복문으로 모든 간선에대한 방문을통해서 해당 노드가 사이클이 있는지 없는지 확인
2.  V가 최대 100번밖에 되지 않음으로, 사이클이 생긴 노드에서 E번노드를 방문할 수 있는 없는지 모두 체크
   1. 성공했다면 "Gee" 출력
   2. 모든 노드에서 실패했다면 해당 노드들을 제외하고 최장거리 다시계산하여 dist[E] 출력

<방법 2>

1.  V-1번 반복문으로 모든 간선에 대한 방문을통해 해당 노드가 사이클이 있는지 없는지 확인
2.  다시한번 V-1 반복문으로 모든 간선에 대한 방문을통해 사이클이 있는 노드와 없는노드를 나누어서 처리
   1. dist[E] 설정된 최댓값이면 "Gee" 출력
   2. 그렇지 않으면 dist[E] 출력

  dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";

 

(v가 100밖에 되지 않기때문에 다른 많은 방법들이 존재할것 같습니다.)

---

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
#define MAX_N 101
typedef long long ll;
vector<pair<int, int> > vec[MAX_N];
int earn[MAX_N];
ll dist[MAX_N];
bool visit[MAX_N];
void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

int main() {
     int N, S, E, M;
     cin >> N >> S >> E >> M;
     for (int i = 0; i < N; i++) {
          dist[i] = LONG_MIN;
     }
     for (int i = 0; i < M; i++) {
          int s, e, c; cin >> s >> e >> c;
          vec[s].push_back({ e, -1 * c });
     }

     for (int i = 0; i < N; i++) {
          cin >> earn[i];
     }

     DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

     for (int i = 0; i < N; i++) {
          for (int j = 0; j < vec[i].size(); j++) {
               vec[i][j].second += earn[vec[i][j].first];
          }
     }


     dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";
}code