[백준] 1219. 오민식의 고민 (Java)

 

1219번: 오민식의 고민

풀이

이해가 안됐는데 이 블로그를 참고하여 겨우 이해할 수 있었다...

벨만-포드를 이렇게도 풀 수 있구나 했던 문제

• 특이하게 negative cycle이 아닌 positive cycle을 찾는 문제이다.
• 일반적인 벨만-포드는 N-1까지 최단 경로를 갱신한 후 마지막으로 한번 더 돌아다니면서 사이클 여부를 판정한다.
• 하지만 이 문제에선 사이클이 있는지 검사 뿐만 아니라 시작 지점부터 도착 지점까지의 경로가 있는지도 알아야 한다.
• 따라서 충분한 edge relaxation을 통해 사이클의 존재 여부, 해당 사이클이 도착 지점까지 영향을 미치는지 추가 relaxation이 필요하다.
  • 여기선 N 최대값이 100이므로 N+100번 수행한다.
  • edge relaxation N-1회부턴 만약 positive cycle이 발견되면 해당 노드의 값을 아주 큰 값으로 설정한다. (나는 GEE라고 했음`)
  • 이전 노드가 GEE면 다음 노드도 GEE이다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    // positive cycle
    static int A, B, N, M;
    static long[] dist, val;
    static long[][] adj;
    static final int INF = -100 * 1000000, GEE = 100 * 1000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dist = new long[N];
        val = new long[N];
        Arrays.fill(dist, INF);

        adj = new long[N][N];
        for (long[] arr : adj)
            Arrays.fill(arr, INF);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            adj[from][to] = Math.max(adj[from][to], -weight);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            val[i] = Integer.parseInt(st.nextToken());
        }

        OhMinSik();
        br.close();
    }

    public static void OhMinSik() {
        dist[A] = val[A];

        // 최단경로가 아닌 최대경로 찾기
        for (int n = 0; n < N + 100; n++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dist[i] == INF || adj[i][j] == INF) continue; // 갈 수 없는 경로
                    else if (dist[i] == GEE) dist[j] = GEE; // extra relaxation
                    else if (dist[i] + adj[i][j] + val[j] > dist[j]) {
                        dist[j] = dist[i] + adj[i][j] + val[j]; // edge relaxation
                        if (n >= N - 1) dist[j] = GEE; // positive cycle
                    }
                }
            }
        }
//        System.out.println("dist: " + Arrays.toString(dist));

        if (dist[B] == INF) System.out.println("gg");
        else if (dist[B] == GEE) System.out.println("Gee");
        else System.out.println(String.valueOf(dist[B]));

        return;
    }
}