백준 1219 오민식의 고민 c++

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

(SPFA 연습을 위해 벨만 포드로 풀 수 있는 문제 중 선택을 해보았다.)

 

민식이는 특정 시작점에서 도착점까지 가는 경로마다 비용이 있고, 노드에 도착하면 돈을 법니다. 

 

문제를 다음과 같이 치환할 수 있습니다. 

a node -> b node 비용 cost, b node 도착 시 버는 돈 earn : a -> b 갔을 때 버는 금액 = earn - cost

도착 지점에 도달했을 때 버는 최종 금액을 최대로 하도록 하여라. 

 

시작점에서도 버는 금액이 포함되는 건지가 햇갈렸는데 test case 5번을 보면 포함됨을 알 수 있습니다. 

(7만큼 0번에서 번다, 0번에서 0번으로 갈 때는 10의 cost가 든다. => 답 7 => 처음 0번 시작할 때부터 7만큼 벌고 시작함)

 

cost가 더 큰 경우, 버는 금액이 음수이므로, 벨만 포드 또는 SPFA로 풀 수 있고, SPFA로 풀었습니다. 

 

로직은 다음과 같습니다. 

1. 도착지점까지 갈 수 있는 지 체크한다. (노드 50개, 엣지 50개 밖에 없으므로 별 무리 없음) (gg 체크)

2. SPFA로 각 노드까지 최대 버는 금액을 계산한다. (코드 상 dist) (일반적으로는 최소 거리이지만, 업데이트 기준만 max로 업데이트 하면 됨) 

3. 업데이트된 노드가 큐에 존재하는 지 체크한다. 큐에 없는 경우만 고려한다. (벨만 포드와의 차이점) (큐에 있는 거는 어짜피 다음 차례에 해당 노드 기준으로 업데이트 진행하므로 중복해서 계산할 필요 없음. 원하는 값 업데이트만 하면 됨) 

4. 사이클 발생하는 지 체크한다. 단, 단방향이므로 사이클이 발생한 노드에서 도착 노드까지 경로가 없을 수도 있다. 

사이클이 있으면서 도착지점까지 경로 있으면 Gee를 출력한다. 

5. 사이클 없으면 다음 기준 노드를 큐에 추가한다. 

 

코드는 아래와 같습니다. 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// SPFA로 계산하면서 버는 것까지 고려해서 업데이트 여부 결정해야 함 
// 음수 사이클 대신 무한 사이클 여부 고려해야 함 

int n, m;
int start, finish;
long long inf = -987654321;

vector<pair<int, long long>> graph[50];
queue<int> q;
bool inQueue[50];
long long earn[50];
long long dist[50];
int cycleCount[50];

void init() {
    cin >> n >> start >> finish >> m;

    int from, to;
    long long cost;
    for(int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        graph[from].push_back({to, -1 * cost});
    }

    for(int i = 0; i < n; i++) {
        cin >> earn[i];
        inQueue[i] = false;
        dist[i] = inf;
        cycleCount[i] = 0;
    }

    // 버는 금액과 가는 비용 미리 상쇄해서 계산 
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < graph[i].size(); j++) {
            graph[i][j].second += earn[graph[i][j].first];
        }
    }
}

bool possible(int startNode, int finishNode) {
    // gg case 체크 
    queue<int> que; 
    bool visited[50];
    for(int i = 0; i < n; i++) visited[i] = false;

    que.push(startNode);
    visited[startNode] = true;

    while(!que.empty()) {
        int cur = que.front();
        que.pop();

        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            if(visited[next] == false) {
                que.push(next);
                visited[next] = true;
            }
        }
    }

    // 방문할 수 있는 지 여부 체크 
    if(visited[finishNode]) return true;
    return false;
}

int SPFA() {

    q.push(start);
    dist[start] = earn[start];
    inQueue[start] = true;
    cycleCount[start] = 1;

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        inQueue[cur] = false;

        long long d = dist[cur];

        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            long long cost = graph[cur][i].second;

            // 업데이트 되는 경우
            if(dist[next] < (d + cost)) {
                dist[next] = (d + cost);

                // 다음 노드 큐에 없음
                if(inQueue[next] == false) {

                    // 사이클 있는 경우 (무한대 증가 가능)
                    // 사이클 있는데에서 finish까지 가는 경로 있으면 -1 리턴 
                    // 사이클 없으면 큐에 넣기 
                    if((cycleCount[next] + 1) >= n) {
                        // Gee case
                        bool chk = possible(next, finish);
                        if(chk) return -1;
                    } else {
                        q.push(next);
                        inQueue[next] = true;
                        cycleCount[next]++;
                    }
                }
            }
        }
    }

    // 도착 못 함 
    // gg case
    if(dist[finish] == inf) {
        return 0;
    }

    return 1;
}

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

    init();

    bool chk = possible(start, finish);
    if(chk == false) {
        cout << "gg";
        return 0;
    }

    int res = SPFA();
    if(res == -1) cout << "Gee";
    else if(res == 0) cout << "gg";
    else cout << dist[finish];

    return 0;
}