[BOJ알고리즘, C++]#1219_오민식의 고민, 최단 경로, 최대 경로, 길 찾기, 벨만-포드

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 벨만-포드 알고리즘

[알고리즘]#2_길 찾기 알고리즘

벨만-포드 알고리즘은 음수 가중치를 포함하는 그래프에서 '단일-출발' 혹은 '단일-쌍' 최단 경로를 구하는 알고리즘입니다. 일반적으로, 벨만-포드 알고리즘은 간선 목록 순회 N-1번 + 순환 여부 검사 N번으로 구현됩니다. 벨만-포드 알고리즘의 시간 복잡도는 O(|E| x |V|)으로 상수 시간입니다. 

 

2. 최단 경로가 아니라, 최대 경로라고 오잉?

1. 먼저, 이익과 비용 계산을 통해 '음수' 가능성이 존재하며, 사이클 여부가 불확실하므로 '단일-쌍' 최단 경로 알고리즘은 '벨만-포드' 활용이 적절해 보인다.
2. 그리고, 이익과 비용 계산을 통해 이익을 최대화하기 위해선 '이익'을 음수 값으로, '비용'을 양수 값으로 설정하여 벨만-포드 알고리즘을 구현해 주면 됩니다.
3. "Gee"는 무한히 많은 돈을 벌 수 있다. 벨만-포드 알고리즘을 통해 '음수 사이클(이익이 계속 발생하는 순환 구조)'이 발견되면, 해당 사이클로부터 도착 도시로 연결되는 경로가 존재할 때 돈을 무한히 벌 수 있습니다. 따라서, 벨만-포드 수행 후 음수 사이클을 구성하는 정점 목록을 구성하고, 이들에 대하여 BFS를 수행하여 이들 중 어느 하나라도 도착 도시와 연결되는 경로가 존재하면 "Gee"를 출력해 줍니다.
4. "gg"는 출발 도시 -> 도착 도시의 경로가 존재하지 않을 때 출력합니다. 따라서, 벨만-포드 알고리즘 수행, 음수 사이클 여부 체크, 음수 사이클 구성 정점들에 대한 BFS 수행 후, 도착 도시의 최단 경로 값이 업데이트되지 않고 초기 값을(LLONG_MAX) 가질 경우, "gg"를 출력해 줍니다.

 

---

 

#3. 콛

/*
    @문제: 시작점과 도착점을 잇는 경로 중 최대 경로 값을 갖는 경로를 찾고, '사이클'여부 검사를 통해 무한히 값이 업데이트 되는지 체크
    @설명
        1. Bellman-Ford 활용: "단일-쌍" 혹은 "단일 출발" 최단 경로 알고리즘, 음수 가중치가 포함된 그래프에 활용
        2. 주의할점: 최단 경로 알고리즘을 통해 '최대 경로'값을 찾는 유형
        3. Bellman-Ford 시작 시 dist[start] 값을 '0'이 아니라, -profit[dstart]로 설정하여 기존의 dist[start] 값을 이익이 아니라 비용으로 전환해서 설정
        4. if (dist[u] != LLONG_MAX && dist[u] + cost < dist[v]), 기존의 최단 경로 업데이트 조건과 동일하게 가지만, '최대 경로'를 찾을 경우
            cost 값을 "edges[j].cost - profit[v]" 처럼 설정하여, 최단 경로 -> 최대 경로 값 업데이트 조건으로 변경 가능.
        5. Bellman-Ford 활용 최대 경로 값 알고리즘에서 사이클 여부 확인과 더불어, 도착점과 연결되어 있는 경로 중 '양수 사이클'이 존재하는지 추가적으로 확인하기 위해서
            도착점을 시작 정점으로하는 BFS를 통해 '사이클'을 형성하는 각 정점들과 도착 정점 사이에 경로가 존재하는지 확인해줍니다. 
*/

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

struct Edge {
    int from;
    int to;
    int cost;
};

int main() {
    int n, start, end, m;
    cin >> n >> start >> end >> m;
    
    vector<Edge> edges(m);
    vector<long long> dist(n, LLONG_MAX);
    vector<bool> reachable(n, false);
    
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].cost;
    }
    
    vector<int> profit(n);
    for (int i = 0; i < n; i++) {
        cin >> profit[i];
    }
    
    dist[start] = -profit[start];
    
    // 벨만 포드: 음수 가중치, N-1번과 N번째 업데이트
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].from;
            int v = edges[j].to;
            int cost = edges[j].cost - profit[v];
            if (dist[u] != LLONG_MAX && dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
            }
        }
    }
    
    // 사이클 여부 검사
    bool hasNegativeCycle = false;
    vector<bool> inCycle(n, false);
    for (int j = 0; j < m; j++) {
        int u = edges[j].from;
        int v = edges[j].to;
        int cost = edges[j].cost - profit[v];
        if (dist[u] != LLONG_MAX && dist[u] + cost < dist[v]) {
            inCycle[v] = true;
            hasNegativeCycle = true;
        }
    }
    
    // BFS: 사이클 경로에 포함되는 각 정점들이 도착점과 연결되는 경로를 가지고 있는지 확인
    queue<int> q;
    vector<bool> visited(n, false);
    if (hasNegativeCycle) {
        for (int i = 0; i < n; i++) {
            if (inCycle[i]) {
                q.push(i);
                reachable[i] = true;
                visited[i] = true;
            }
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int j = 0; j < m; j++) {
                if (edges[j].from == u && !visited[edges[j].to]) {
                    visited[edges[j].to] = true;
                    reachable[edges[j].to] = true;
                    q.push(edges[j].to);
                }
            }
        }
    }
    
    if (reachable[end]) {
        cout << "Gee" << endl;
    } else if (dist[end] == LLONG_MAX) {
        cout << "gg" << endl;
    } else {
        cout << -dist[end] << endl;
    }
    
    return 0;
}

 

---