[BOJ] 1219. 오민식의 고민 (18.8.22 그림 추가)

오민식의 고민

클릭시 이동합니다.

어떻게 풀까?

으악... 저는 dfs와 bfs를 이용해서 풀었는데... 알고보니 벨만-포드 알고리즘이었어요..

이따가 벨만-포드로 풀어서 해당 방법도 업데이트 하겠습니다. 버전 1과 2로 나누죠!

Version.1 DFS and BFS

노드가 100개밖에 없으니 DFS를 이용해서 최댓값을 구해봅시다.

잘 생각해보면, 해당 문제에서 양수 사이클이 생겨서 무한이 생기는 경우는, 

방문했던 점을 또 방문할 경우에만 생깁니다.

더 정확하게 말하면, 양수 사이클이 생겼을 경우이죠.

반대로, 음수 사이클이 생기는 경우에는 싸이클의 반복 경로를 탄다면, 가격이 계속 줄어든다는 것을 알 수 있죠!

결국, 음수 사이클이 생기는 경우에는 반복 경로를 타지 않고 가는 것이 최대 수익을 얻는 경우입니다.

반복 경로를 탔는데 가격이 그대로인 경우는 어떨까요?

반복 경로를 타던, 안타던 결국 도착점까지 도달했을때의 가격은 변화가 없을 겁니다!

한 마디로, 우선은 반복 경로 없이 시작점에서 도착점까지 벌 수 있는 최댓값을 구한 다음에 이 값을 저장하고,

도착 지점까지 양수 사이클이 생기는지 검사해주면, 어떤 것이 답이 될 지 정할 수 있는 것입니다!

이 경우에는 visit 배열을 사용하면서 dfs를 통해 이전에 방문했던 마을은 다시 안 방문하면 됩니다!

또한, 생각보다 쉽게 dfs를 하면서 양수 사이클이 생기는지도 검사해 줄 수 있습니다!

양수 사이클이란, 이미 방문했던 점을 다시 방문했는데 방문했을 때보다 현재 값이 커진 경우이죠!

이렇게 되면, 방문했던 곳을 계속 타면 점점 돈벌이가 늘어난다는 것을 알 수 있습니다!

위의 그림을 보시면, 처음 노드에서 0원 이었지만, 다음 노드들을 타면서 20원이 되었습니다!

즉, 해당 노드를 계속 타면 돈이 점점 증가한다는 것을 알 수 있죠!

이 싸이클을 한 번 더 타면 40원이 되고, 60원이 되고,, 부자가 될 겁니다!

그럼 이렇게 되면, 현재 양수 사이클이 생긴 곳들에 대한 정보를 알 수 있습니다.

하지만 위 그림에서처럼, 양수 사이클의 시작점을 알게된 것일 뿐, 아직 전체적인 마을에 대해서 양수 사이클이 생기는지는 확인하지 않았습니다.

이는, 양수 사이클이 생긴 곳의 노드들을 BFS를 돌리면, 이제 무한대의 돈을 벌 수 있는 노드들이 어디인지 알 수 있습니다!!!

위 그림의 경우에는 모든 마을에서 무한의 돈을 벌 수 있는 것이죠!

이렇게, 무한의 돈을 벌 수 있는 마을들을 BFS를 통해 쫙쫙 퍼뜨려 나가면, 도착지점의 마을이 무한대의 수익을 얻을 수 있는지, 아니면 평범한 수익을 얻을 수 있는지 알 수 있습니다! 

마지막으로, 최대 금액이 평범한 수라면 그 수를 출력하고, 무한대면 Gee를, 만약 방문하지 못했다면 gg를 출력하면 됩니다!!!!

5 0 4 5
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10

위 예제를 한번 풀어봅시다.

출발점을 초록색, 도착점을 자주색으로 나타내겠습니다.

처음에 벌 수 있는 돈이 0이기 때문에 출발지점에서는 빵원부터 시작합니다!

요금과 벌이가 같으므로, 다음 도시에서도 빵원이죠.

또 빵원 입니다.. 슬슬 불쌍해지네요...

오옷 드디어 배건이 됐습니다!!

엇! 처음으로 돌아가는데, 이미 방문한 지점입니다. 심지어 돈이 처음 0번 노드를 방문했을 때보다 더 늘어났습니다!

이는 양수 사이클이 됐음을 의미하기 때문에 0번 노드는 무한대의 돈을 벌 수 있습니다!!

더 이상 갈 노드가 없기 때문에, 2번 노드로 돌아옵니다.

이렇게 되면, 도착 지점까지 우선 벌 수 있는 최대의 돈은 0 원이 된다는 것이죠! (양수 사이클이 없을 경우)

하지만, BFS를 통해 0번 노드부터 무한대로 돈을 벌 수 있는 노드들을 찾아나간다면..! 결국 도착지점에서 벌 수 있는 돈은 무한대라는 것을 금방 알 수 있을 것입니다!

하지만, 아래와 같은 경우는 어떨까요?

아래와 같은 상황에서는, 결국 양수 사이클이 결과값에 오지 못하기 때문에 도착지점까지 벌 수 있는 최대 금액인 10이 출력될 것입니다!!

코드

#pragma once
#include<cstdio>
#define INF 98764321
 
int que[10000], m, n, st, dt;
int adj[100][100][2], alen[100];
int earn[100];
int check[100];
bool visit[100];
int res = -INF;
 
 
void dfs(int now, int e) {
    if (now == dt) {
        res = res < e ? e : res;
    }
 
    for (int i = 0; i < alen[now]; i++) {
        int next = adj[now][i][0];
        int cost = adj[now][i][1];
 
        if (visit[next] && check[next] != INF && check[next] < e - cost + earn[next]) {
            check[next] = INF;
            e = INF;
        }
 
        if (!visit[next]) {
            visit[next] = true;
            if(e != INF) check[next] =e - cost + earn[next] > check[next] ? e - cost + earn[next] : check[next];
            else check[next] = INF;
 
            dfs(next, e == INF ? INF : e - cost + earn[next]);
            
            check[next] = check[next] == INF ? INF : -INF;
            visit[next] = false;
        }
    }
}
 
void makeINF(int st) {
    int f = 0, r = 0;
 
    que[r++] = st;
    visit[st] = true;
 
    while (f != r) {
        int now = que[f++];
 
        for (int i = 0; i < alen[now]; i++) {
            int next = adj[now][i][0];
 
            if (check[next] != INF) {
                check[next] = INF;
                visit[next] = true;
                que[r++] = next;
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d  %d\n", &n, &st, &dt, &m);
    for (int i = 0; i < n; i++) {
        check[i] = -INF;
    }
    while (m--) {
        int from, to, cost;
        scanf("%d %d %d\n", &from, &to, &cost);
        adj[from][alen[from]][0] = to;
        adj[from][alen[from]++][1] = cost;
    }
 
    for (int i = 0; i < n; i++) scanf("%d \n", &earn[i]);
 
    check[st] = earn[st];
    
    visit[st] = true;
    dfs(st, earn[st]);
    visit[st] = false;
 
    for (int i = 0; i < n; i++) {
        if (visit[i]) continue;
        if (check[i]!= INF) continue;
 
        makeINF(i);
    }
    if (check[dt] == INF) {
        printf("Gee\n"); 
        return 0;
    }
    else if (res == -INF) {
        printf("gg\n"); 
        return 0;
    }
 
    printf("%d\n", res);
    return 0;
}

여담

시간복잡도는 dfs에서의 부분문제가 N개가 나오고, 내부에서 for문이 N번까지 나올 수 있기 때문에 대략 입니다.

Version.2 벨만-포드 알고리즘

벨만 포드에서는 사이클을 찾기가 쉽습니다!

바로, N번 돌렸을 때, 이전의 값보다 커지는 노드가 바로 양수 사이클인 것이죠!

이유가 무엇일까요?

설명하기 위해서 '비둘기집의 원리'를 이용할 수 있습니다.

일단 노드 A에서 B로 가는 간선의 개수가 X개면, 지나는 노드는 X+1개 입니다!

이유는.. 그림을 그려보면 쉽게 나옵니다.

간선이 하나가 늘면, 노드가 하나가 늘게되죠! 그리고 노드가 1개일때 간선은 0개이기 때문에 간선이 X개면 노드는 X+1개가 된다는 것입니다!

여기서, 만약 간선의 개수가 N보다 같거나 크면 어떨까요?!

그렇다는 것은, 노드의 개수는 N+1 이상이라는 것입니다!

그리고, 비둘기집의 원리에 의해서 노드는 N인데 반해서, N+1개의 노드를 매칭시켜야 하기 때문에 두 번 나오는 노드가 꼭 존재하는 것이죠!

예를 들면, 노드의 개수는 5 개인데, 지나온 노드가 6개라고 합시다!

그리고, 해당 경로의 노드가 최대수익이 더 올라서 갱신됐다고 하겠습니다!

그렇다면, 모든 노드를 하나씩 지난다고 해보겠습니다.

1 - 2 - 3 - 4 - 5 - ?

모든 노드를 하나씩 지난다고 해도 6개의 노드를 지날 수가 없습니다.

하나의 노드를 더 지나야 하려면 1,2,3,4,5 중에 하나의 노드를 더 지나와야 할 것입니다!

한번 '?' 를 4번이라고 해보죠!

그리고, 4 번으로 돌았을 때, 최대 수익이 갱신됐다고 하겠습니다!

편의상, 4 까지 왔을 때의 수익은 0,

4-> 5로 가면서 벌 수 있는 비용은 1

5 -> 4로 가면서 벌 수 있는 비용은 1이라고 하겠습니다!

1 - 2 - 3 - 4 - 5 까지의 경로를 오면서 5번 노드까지 벌 수 있는 최대 수익은 0 -> 1로 최신화 되었습니다.

그리고 5 -> 4로 가면서 벌 수 있는 비용이 1이기 때문에, 4번 노드까지 가면서 벌 수 있는 최대 금액은 0 -> 2로 최신화 됩니다!

또 다시, 4 -> 5로 가면서 벌 수 있는 수익은 1이기 때문에, 5번 노드까지 벌 수 있는 금액은 1 증가합니다!

이러한 구조가 반복되면서, 사이클이 생기는 4번 5번 노드는 무한대의 금액을 버는 것입니다!

그리고, 4번 노드와 5번 노드와 연결된 노드들은 모두 무한대의 금액을 벌 수 있게 되는 것이죠!!

위 내용을 보면 알 수 있듯이, 

벨만-포드 알고리즘을 N번 돌렸는데, 업데이트가 된다면,  업데이트 된 X와 싸이클을 이루게 되는 한 지점이 있다는 것이고,

해당 싸이클은 X - .. - X 순으로 방문할 것입니다!

따라서, 마지막 X에서 또 다시 X - ... - X 순으로 방문 한다면, 무한(INF)의 수익을 낼 수 있다는 것을 알 수 있죠!

그리고, 해당 노드에서 방문할 수 있는 모든 노드들을 BFS로 연결하면, 최대 수익이 무한대가 되는 노드들을 알 수 있는 것이죠!

길게 설명했지만, 

한줄로 다시 설명하자면, 만약, 벨만-포드 알고리즘을 이용해서 최대 수익을 N번 업데이트 됐는데 최대 수익이 업데이트가 또 됐다면, 해당 업데이트된 노드는 양수 사이클을 가지는 노드이다! 라는 것이죠.

왜냐하면, N번 업데이트 했다는 것은, 시작점에서 간선을 N번 이동했는데 업데이트 됐다는 것이고,

이는, 노드는 N+1번 이동했다는 것입니다.

노드를 N+1번 이동했다는 것은, 비둘기집의 원리에 의해 반복적으로 방문한 노드가 있다는 것이죠.

그리고 반복적으로 방문한 노드 사이가 바로 양수 싸이클을 이루는 부분입니다! 

위의 노드에서 약간 노드를 추가하여 한번 무한의 수익을 버는 노드들이 어디인지 확인해 봅시다.

 해당 그래프에서 노드는 8개이기 때문에, 출발점이 1일 경우에 8번의 간선을 타면,

1 - 2 - 3 - 4 - 5 - 4 - 5 - 4 - 5 이 계속 업데이트 될 것입니다. 그리고, 5번이 무한(INF)의 값을 가진다는 것을 알 수 있습니다!

그럼, 이제 INF를 알았으니, INF와 연결된 모든 점은 마찬가지로 INF일 것입니다!

BFS를 통하면 아래와 같은 그림을 얻을 수 있을 것입니다!

자, 이제 해당 지점이 모두 무한대의 값을 가지는 지점들입니다!

벨만-포드 알고리즘이 간선을 노드 수 만큼 돌리는 이유도 여기서 나오는 것입니다!

1번 돌려서 업데이트가 되면, 출발 지점에서 1번 이동한 것을 업데이트 한 것이고,

2번 돌려서 업데이트가 되면, 출발 지점에서 2번 이동한 것 까지의 최댓값을 찾은 것이라고 할 수 있죠!

따라서, N번 돌려서 업데이트가 되면, 출발 지점에서 N번 이동한 노드들 까지의 최댓값을 찾은 것이고, 여기서 업데이트가 됐다는 말은, 사이클이 있다는 말인 것입니다!!!

이제, N번 돌렸을때 업데이트된 노드들의 값들을 저장한 뒤에, BFS를 돌려줘서 값이 무한이 되는 노드들을 찾아주면,

결과 값이 gg인지, 일반적인 수인지, Gee인지 알 수 있겠죠!

코드

#pragma once
#include<cstdio>
#define INF 98764321
 
int que[10000], m, n, st, dt;
int adj[100][100][2], alen[100];
int earn[100];
long long check[100], check2[100];
int edge[100][3];
 
void makeINF(int st) {
    int f = 0, r = 0;
 
    que[r++] = st;
 
    while (f != r) {
        int now = que[f++];
 
        for (int i = 0; i < alen[now]; i++) {
            int next = adj[now][i][0];
 
            if (check[next] != INF) {
                check[next] = INF;
                que[r++] = next;
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d  %d\n", &n, &st, &dt, &m);
    for (int i = 0; i < n; i++) {
        check[i] = -INF;
        check2[i] = -1;
    }
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d\n", &edge[i][0], &edge[i][1], &edge[i][2]);
        adj[edge[i][0]][alen[edge[i][0]]][0] = edge[i][1];
        adj[edge[i][0]][alen[edge[i][0]]++][1] = edge[i][2];
    }
 
    for (int i = 0; i < n; i++) scanf("%d \n", &earn[i]);
 
    check[st] = earn[st];
 
    bool update = true;
    int cnt = n;
 
    while (cnt-- && update) {
        update = false;
 
        for (int i = 0; i < m; i++) {
            int now[3] = { edge[i][0], edge[i][1], edge[i][2] };
 
            if (check[now[0]] == -INF) continue;
 
            if (check[now[0]] + earn[now[1]] - now[2] > check[now[1]]) {
                update = true;
                check2[now[1]] = cnt;
                check[now[1]] = check[now[0]] + earn[now[1]] - now[2];
            }
 
        }
    }
 
    if (update) {
        for (int i = 0; i < n; i++) {
            if (check2[i] != 0) continue;
            if (check[i] == INF) continue;
            makeINF(i);
        }
    }
 
    if (check[dt] == INF) {
        printf("Gee\n");
        return 0;
    }
    else if (check[dt] == -INF) {
        printf("gg\n");
        return 0;
    }
 
    printf("%d\n", check[dt]);
    return 0;
}

여담

간선 M개를 N번 만큼 돌리기 때문에, 시간 복잡도는 O(MN) 입니다!