오민식의 고민

문제 분석 및 풀이

설계 분석

• 간선 정보와 최댓값(최솟값)을 구하라는 이야기가 있어서 일단 최단거리 알고리즘을 생각했다.
• 경로의 중복이 가능하고 돈을 무한히 가지고 있을 수 있는 경우가 있다는 것으로 보아 사이클을 판별하는 문제라고 생각했다.
• 최단경로와 사이클 둘다 관련있는 벨만 포드를 떠올리게 되었고 여기서는 음의 사이클이 아니라 양의 사이클이 있는지 확인해야 한다. (돈을 무한히 가지는 경우에서 힌트를 받음)
• 모든 간선을 검사 하면서 더 큰 값으로 갱신 (N-1번)
• 마지막으로 검사
  • 여기서 갱신되는 노드는 사이클에 포함
• 사이클에서 목적지로 갈 수 있으면 돈을 무한히 가질 수 있음
  • 출발 - 종료 경로 사이에 사이클이 있다는 뜻

구현은 생각보다 금방 끝났지만 통과까지는 엄청난 시간이 걸렸다. 중간에 정답 코드와 비교하면서 어디가 잘못되었는지 비교했는데 아무리봐도 맞는 풀이어서 난감했었는데 질문게시판을 모두 읽어보다가 발견했다.

'같은 경로에 다른 값이 들어오는 경우가 있다'

문제에서 여러 교통 수단을 이용할 수 있다고 이야기한 것을 위와 같은 상황이 생길 수 있다고 생각하면 솔직히 나는 자신 없다. 그래도 경험 해봤으니 문제를 주의 깊게 읽어야 할듯.

여튼 간선을 기록했다면 별로 문제가 없었겠지만 나는 인접 행렬로 그래프 정보를 저장해서 간선의 값이 덮어씌워지는 현상이 생겼고 50%에서 무한 실패를 경험했다. 그 뒤에 큰 값을 유지하도록 바꿔 간단히? 해결했다. 간선을 벡터에 담아서 사용했다면 자연스레 중복된 경로가 여러개 존재해 알아서 갱신 되었겠지...
개인적으로 디버깅할 때 값을 보기 편해서 인접행렬을 선호 했는데. 앞으로는 주의 해야겠다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <queue>
using namespace std;

const long long MAX = 987654321;
int N, M, start, dest;
int income[50];
int graph[50][50];
long long dist[50];

void Bellman_Ford(int start)
{
    fill(dist, dist+N, -MAX);
    dist[start] = income[start];
    
    // N-1번 반복
    for (int k=0; k<N-1; k++)
    {
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<N; j++)
            {
                if(graph[i][j] == -MAX || dist[i] == -MAX) continue;
                if(dist[i] + graph[i][j] >= dist[j])
                {
                    dist[j] = dist[i] + graph[i][j];
                }
                
            }
        }
    }

    
    int before  = dist[dest];
    // 여기서 갱신되는 노드는 사이클에 포함
    vector<int> cycle;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            if(graph[i][j] == -MAX || dist[i] == -MAX) continue;
            if(dist[i] + graph[i][j] > dist[j])
            {
                cycle.push_back(j);
                dist[j] = dist[i] + graph[i][j];
            }
                
        }
    }

    int after  = dist[dest];

    // 경로가 없으면
    if(dist[dest] == -MAX)
    {
        cout << "gg\n";
    }
    // 목적지까지의 값이 갱신 되었으면 (도착점이 사이클에 포함되는 경우)
    else if (before != after)
    {
        cout << "Gee\n";
    }
    else
    {
        // 사이클에서 도착점 까지 갈 수 있는지 판단.
        queue<int> q;
        vector<bool> visited(N,false);
        for (auto e : cycle)
        {
            visited[e] = true;
            q.push(e);
        }

        while(!q.empty())
        {
            int u = q.front(); q.pop();
            if (u == dest) 
            {
                cout << "Gee\n";
                return;
            }
            for (int v=0; v<N; v++)
            {
                if (graph[u][v] == -MAX) continue;
                if (visited[v]) continue;
                visited[v] = true;
                q.push(v);
            }
        }
        cout << dist[dest] <<"\n"; 
    }

}

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

    fill(&graph[0][0], &graph[0][0]+(50*50), -MAX);
    cin >> N >> start >> dest >> M;
    
    // 그래프 초기화
    for (int i=0; i<M; i++)
    {
        int u,v,weight;
        cin >> u >> v >> weight;
        // 동일 경로에 다른 값이 들어오는 경우가 있네... 허허....
        // 이것때문에 3시간 날렸네ㅋㅋㅋㅋ
        // 간선 리스트로 할걸...
        graph[u][v] = max(graph[u][v], -weight);
    }

    
    // 각 도시에 도착했을때 얻는 돈을 최신화
    for (int i=0; i<N; i++)
    {
        int weight;
        cin >> weight;
        income[i] = weight;
        for (int j=0; j<N; j++)
        {
            if (graph[j][i] != -MAX)
            graph[j][i] += weight;
        }

    }

    Bellman_Ford(start);


    return 0;
}