[BOJ] 1219 오민식의 고민

date

Feb 7, 2022

slug

boj-1219

author

status

Public

문제

1219번: 오민식의 고민

오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

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

풀이

벨만-포드 문제이다. 정점은 벌수 있는 돈(양수), 간선은 비용(음수)로 인식해서 풀었다.

이 문제에서 나올 수 있는 출력 값은 크게 세 가지이다.

1. 도착 도시에 도착하지 못할 경우 -> gg 출력 2. 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 올 수 있는 경우 -> Gee 출력 3. 도착 도시에 도착했을 때 가지고 있을 수 있는 최대 액수 -> 액수 출력

나는 dis를 임의의 작은 음수로 초기화 해주었다. 그리고 시작 노드에 대한 값(dis[S])을 시작 노드에서 벌 수 있는 금액으로 시작하였다.

그리고 현재 노드를 거쳐서 다음 노드로 가는 경우 돈을 더 많이 벌 수 있다면 갱신 시켜 주었다.

N번째에서도 갱신이 된다면 양의 순환이 일어나는 것으로 판단하였고, 이럴 경우 양의 사이클 내에 도착 지점이 포함되어 있는지를 판단하였다. 만약 양의 사이클 내에 도착 지점이 있을 경우 위에서 두번째 경우에 해당한다.

벨만-포드가 끝나고 도착 도시에 도달하지 못했을 경우를 dis[E] == INF로 판단하여 1번 케이스를 출력해주었다.

코드


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF -100000000000
using namespace std;
typedef long long ll;
typedef pair<int, long> pil;

int n, m, S, E, s, e;
ll t;
vector<pil> graph[50];
ll arr[50];
ll dis[50];
int vis[50];

int isVis(int start) { // start노드부터 E노드까지의 경로가 있는지 확인하는 BFS(너비 우선 탐색)
    if (start == E) return 1;
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(start);
    vis[start] = 1;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for(int i = 0; i < graph[cur].size(); i++) {
            int nxt = graph[cur][i].first;
            if (vis[nxt]) continue;
            if (nxt == E) return 1;
            vis[nxt] = 1;
            q.push(nxt);
        }
    }
    return 0;
}

int go() {
    dis[S] = arr[S]; // 노드S 부터 출발
    for(int i = 0; i < n; i++) {
        for(int cur = 0; cur < n; cur++) {
            if (dis[cur] == INF) continue; // 아직 방문하지 않은 노드에 대해선 넘긴다.
            for(int j = 0; j < graph[cur].size(); j++) {
                int nxt = graph[cur][j].first;
                ll cost = graph[cur][j].second;
                if (dis[nxt] < dis[cur] + cost + arr[nxt]) { // 만약 다음 노드의 dis가 cur을 경유해서 가는 것보다 적다면 갱신시켜준다.
                    if (i == n - 1) { // 양의 사이클이 발생했을 때
                        if (isVis(nxt)) return 1; // nxt부터 도착지점인 E까지의 사이클이 있는지 확인한다. 있다면 무한대로 커질 수 있으므로 1을 리턴한다.
                    }
                    dis[nxt] = dis[cur] + cost + arr[nxt];
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d %d %d %d", &n, &S, &E, &m);
    for(int i = 0; i < n; i++) dis[i] = INF; // 주의할 점은 INF는 음수라는 것
    for(int i = 0; i < m; i++) {
        scanf("%d %d %lld", &s, &e, &t);
        graph[s].push_back({e, -t});
    }
    for(int i = 0; i < n; i++) scanf("%lld", &arr[i]);
    if (go()) printf("Gee");
    else {
        if (dis[E] == INF) printf("gg"); // E노드에 방문하지 못했다는 뜻이므로 gg 출력
        else printf("%lld", dis[E]);
    }
}