백준 - 1219 : 오민식의 고민

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

 

문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다.

 

출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다.

도착이 가능할 경우 소지금의 최댓값
도달 자체가 불가능할 경우 "gg" 출력
도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력

이 케이스들을 개별적으로 생각해보자.

 

첫 번째는 이익이 최대로 되는 경로를 찾으면 된다.

 

두 번째는 도달 가능성을 판단하면 된다.

 

세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다.

 

즉 세가지를 종합했을 때 음수 사이클을 판별할 수 있는 벨만 포드와 도달 가능성을 확인할 수 있는 플로이드 워셜 알고리즘의 혼합을 통해 문제를 풀 수 있음을 짐작할 수 있다.

 

입력으로 주어지는 도시의 개수는 100개 이하이므로 플로이드 워셜이 이용돼도 시간 복잡도에 큰 영향을 미치지 않을 것이다.

 

우선 도달 가능성을 판단하는 플로이드 워셜 알고리즘을 작성한다.

void floyd(int vx)
{
    for (int c = 0; c < vx; ++c)
        for (int i = 0; i < vx; ++i)
            for (int j = 0; j < vx; ++j)
                if (am[i][c] && am[c][j])
                    am[i][j] = 1;
}

3중 for를 순회하면서 도시 i 와 도시 j가 연결 가능하면 1을 대입한다.

 

도달했을 때 소지금을 계산하기 위한 벨만 포드 알고리즘을 작성한다.

l bellford(vector<vector<pa>> &adj, vector<int> &profit, int begin, int goal)
{
    int vtx(adj.size());
    
    vector<l> income(vtx, INF);
    income[begin] = profit[begin];
    bool updated;
    
    // 도달 가능성에 대한 처리를 위해 일단은 도시개수 - 1 번 만큼 그래프 완화 실행
    for (int r = 0; r < vtx - 1; ++r)
    {
        updated = false;
        for (int i = 0; i < vtx; ++i)
        {
            for (auto item : adj[i])
            {
                int next(item.first);
                int pay(item.second);
                
                if (income[i] != INF && income[i] + profit[next] + pay > income[next])
                {
                    income[next] = income[i] + profit[next] + pay;
                    updated = true;
                }
            }
        }
        if (!updated)
            return income[goal];
    }
    
    // trap 벡터를 하나 만들어 준다. 이 벡터에는 이번 완화에도 업데이트된,
    // 즉 사이클에 포함된 노드가 들어간다.
    vector<int> trap;
    
    // 완화 수행
    updated = false;
    for (int i = 0; i < vtx; ++i)
    {
        for (auto item : adj[i])
        {
            int next(item.first);
            int pay(item.second);
            
            // 만약 완화가 수행되었을 경우 해당 도시를 trap에 push
            if (income[i] != INF && income[i] + profit[next] + pay > income[next])
            {
                income[next] = income[i] + profit[next] + pay;
                updated = true;
                trap.push_back(i);
            }
        }
    }
    
    if (updated)
    {
        // 도달 자체가 불가능한가? -> gg를 출력하도록 함
        if (!am[begin][goal])
            return INF;
        else
        // 도달을 할 수 있긴 하는가? -> 연결은 되어있는데 음수 사이클에 빠진 경우이므로
        // 돈을 무한정 벌게 됨. -> Gee 출력
            for (int i = 0; i < trap.size(); ++i)
                if (am[trap[i]][goal])
                    return -INF;
        
        // 당시 너무 피로하여 그냥 넣은 것 같은 줄. 실제론 실행되지 않을 것이다.
        return income[goal];
    }
    else
        return income[goal];
}

 

long long이 사용되는 이유는 다음을 참조한다.

https://www.acmicpc.net/board/view/19561

글 읽기 - 답이 왜 long long type이 필요한지 모르겠어요 ㅜㅜ

 

전체 코드

#include <utility>
#include <vector>
#include <iostream>

using namespace std;
using l = long long;
using pa = pair<int, int>;

const l INF(-10000004000);

int am[100][100] {};

void floyd(int vx);
l bellford(vector<vector<pa>> &adj, vector<int> &profit, int begin, int goal);

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    
    int v, go, reach, e;
    cin >> v >> go >> reach >> e;
    
    vector<pa> tmp;
    vector<vector<pa>> al(v, tmp);
    
    while (e--)
    {
        int start, dest, fee;
        cin >> start >> dest >> fee;
        al[start].push_back(make_pair(dest, -fee));
        am[start][dest] = 1;
    }
    
    vector<int> pros(v, 0);
    for (int i = 0; i < v; ++i)
        cin >> pros[i];
        
    floyd(v);
    l result(bellford(al, pros, go, reach));
    
    if (result == -INF)
        cout << "Gee";
    else if (result == INF)
        cout << "gg";
    else
        cout << result;
}

void floyd(int vx)
{
    for (int c = 0; c < vx; ++c)
        for (int i = 0; i < vx; ++i)
            for (int j = 0; j < vx; ++j)
                if (am[i][c] && am[c][j])
                    am[i][j] = 1;
}

l bellford(vector<vector<pa>> &adj, vector<int> &profit, int begin, int goal)
{
    int vtx(adj.size());
    
    vector<l> income(vtx, INF);
    income[begin] = profit[begin];
    bool updated;
    
    for (int r = 0; r < vtx - 1; ++r)
    {
        updated = false;
        for (int i = 0; i < vtx; ++i)
        {
            for (auto item : adj[i])
            {
                int next(item.first);
                int pay(item.second);
                
                if (income[i] != INF && income[i] + profit[next] + pay > income[next])
                {
                    income[next] = income[i] + profit[next] + pay;
                    updated = true;
                }
            }
        }
        if (!updated)
            return income[goal];
    }
    
    vector<int> trap;
    
    updated = false;
    for (int i = 0; i < vtx; ++i)
    {
        for (auto item : adj[i])
        {
            int next(item.first);
            int pay(item.second);
                
            if (income[i] != INF && income[i] + profit[next] + pay > income[next])
            {
                income[next] = income[i] + profit[next] + pay;
                updated = true;
                trap.push_back(i);
            }
        }
    }
    
    if (updated)
    {
        if (!am[begin][goal])
            return INF;
        else
            for (int i = 0; i < trap.size(); ++i)
                if (am[trap[i]][goal])
                    return -INF;
        
        return income[goal];
    }
    else
        return income[goal];
}

 

열심히 했다.