BOJ#1219 오민식의 고민

BOJ#1219 오민식의 고민

* 문제

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

* 풀이

벨만-포드 최단거리 문제입니다.

간선 cost는 음수이고, 각 노드마다 추가로 돈을 벌 수 있습니다.

원하는 것은 S(시작점)에서 D(도착점)까지 갈 때 최대로 벌 수 있는 돈의 액수를 구하는 것입니다.

일반적으로 문제에서 간선의 cost가 양수로 주어지는 반면,

이 문제에서는 간선 cost가 음수이므로

음수 사이클은 문제가 되지 않고 반대로 양수 사이클인 경우가 문제 됩니다.

벨만-포드 알고리즘에 따라 (엣지수(M)만큼 Relaxation)을 N-1번 반복하고

N번째에도 Relaxation이 되면 사이클이 존재함을 알 수 있습니다.

그러나 우리는 사이클 유무를 판단하는 것이 목적이 아니라

시작점에서 도착점까지 갈 때 돈의 최대 액수를 구해야 합니다.

따라서, (엣지수(M)만큼 Relaxation)을 N번만 반복하는게 아니라 (사이클이 있는지 판단만 하는게 아니라)

충분히 무한대로 발산할 수 있도록 Relaxation을 해줘야 합니다.

아래 케이스의 경우를 생각해보시면 되겠습니다.

3 0 2 4

0 1 9999

1 2 9999

1 1 9999

0 2 0

10000 10000 10000

* 테스트 케이스

4 0 3 4

0 1 0

1 2 0

2 1 0

0 3 10

10 10 10 10

10

4 1 3 4

0 1 0

1 2 0

2 1 0

0 3 10

10 10 10 10

gg

3 0 2 4

0 1 9999

1 2 9999

1 1 9999

0 2 0

10000 10000 10000

Gee

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231219/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        long[] dist = new long[N];
        Arrays.fill(dist, Long.MIN_VALUE);

        Edge[] edge = new Edge[M];
        int[] money = new int[N];

        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edge[i] = new Edge(s, d, -w);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {

            money[i] = Integer.parseInt(st.nextToken());
        }

        dist[S] = money[S];

        // Solve

        // 충분히 Relaxation을 해준다
        for (int i = 0; i < N + 100; i++) {

            for (int j = 0; j < M; j++) {

                if (dist[edge[j].s] == Long.MIN_VALUE) continue; // Relaxation이 불필요한 경우
                else if (dist[edge[j].s] == Long.MAX_VALUE) dist[edge[j].d] = Long.MAX_VALUE; // 무한대로 증가하는 경우
                else if (dist[edge[j].d] < dist[edge[j].s] + edge[j].w + money[edge[j].d]) {

                    dist[edge[j].d] = dist[edge[j].s] + edge[j].w + money[edge[j].d];

                    if (i >= N - 1) dist[edge[j].d] = Long.MAX_VALUE; // 무한대로 증가하는 경우
                }
            }
        }

        if (dist[D] == Long.MIN_VALUE) System.out.println("gg");
        else if (dist[D] == Long.MAX_VALUE) System.out.println("Gee");
        else System.out.println(dist[D]);
    }
}

class Edge {

    int s;
    int d;
    int w;

    Edge(int s, int d, int w) {

        this.s = s;
        this.d = d;
        this.w = w;
    }
}