[자바]백준 1865번 웜홀 [그래프 - 벨만포드][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는 데 걸리는 시간을 의미한다. 그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

예제 입력 1

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

예제 출력 1

NO
YES

알고리즘 분류

• 그래프 이론
• 벨만-포드

문제 설명

백준이가 한 지점에서 출발을 하여 다시 출발한 지점으로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 파악하는 문제이다.

즉, 시간이 되돌아가 있는 경우 = 음의 사이클이 있는 경우 이다.

• 음의 사이클이 있는 경우 (YES)
• 음의 사이클이 없는 경우 (NO)

해설

해당 문제의 포인트는 '한 지점에서 출발'을 하여서가 가장 중요한 포인트이다.

만약 특정한 지점이 정해져있다면, 기존 벨만-포드 문제와 다를 것 없이 최단 경로들을 INF로 초기화해주고 특정한 지점만 0으로 초기화해주고 풀면 음의 사이클을 찾아서 YES or NO를 출력하면 될 것이다.

 

하지만 '한 지점에서 출발' 이기 때문에 기존 방식으로 풀면 '틀렸습니다'가 계속되어 미칠 수 있다.. 나처럼...

 

그렇다면 왜? 기존 방식으로 풀면 틀리는 것일까? 이부분만 알면 어떻게 풀어야 하는지 접근 방법이 생각이 날 것이다.

각 지점이 다 연결되어 있다는 말이 없다.

즉, A - B - C는 연결되어있지만 D - E는 따로 떨어져 있다로 가정해보자.

그렇다면 기존 방식 대로 A = 0 그리고 B, C, D, E = INF로 초기화를 했다면, 

A - B - C만 최단 경로가 업데이트가 되고 D - E는 최단 경로가 업데이트가 안된다.

근데 이때, D - E에 음수 사이클이 존재한다면 어떻게 되는 걸까?

 

정답은 YES인데, 정작 출력은 NO를 해서 틀렸습니다가 출력이 되는 것이다.

 

그렇다면 어떻게? 풀면 될까?

두 가지 정도 풀이 방법이 있다.

1. 모든 정점을 출발점으로 지정해서 음수 사이클을 체크하는 방법 (느리지만 확실한 방법 - O(V^2E))

2. 하나의 정점을 출발점으로 지정해서 음수 사이클을 체크하는 방법

 

각각의 풀이 방식으로 풀어도 되는 이유는?

1번 풀이 방식은 간단하다 모든 정점을 반복문으로 돌려서 벨만 포드 알고리즘을 돌려 음수 사이클을 체크하면 된다.

2번 풀이 방식은 해당문제의 특징을 살려 푸는 방법이다. 해당 문제는 최단 경로를 알아내는 문제가 아니라 음수 사이클을 체크하는 문제이다. 즉, 음수 사이클만 알면 된다는 것이다.

음수 사이클만 알면 되기 때문에 INF초기화, INF 검사하는 부분을 다 갖다 버리면 된다. 그렇다면 위의 예제에서 A - B - C 만 체크하는 게 아니라 D - E도 체크할 수 있게 되어 경로에 음수 사이클이 있는지 판별할 수 있게 된다.

 

1번 방법

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.ArrayList;
public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int INF = Integer.MAX_VALUE;
    static int N;
    static int M;
    static int W;
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            bw.write(result() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static String result() throws Exception {
        return ckMinusCycle() ? "YES" : "NO";
    }

    public static boolean ckMinusCycle() throws Exception {
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken()); //지점의 수
        M = Integer.parseInt(st.nextToken()); // 도로의 개수
        W = Integer.parseInt(st.nextToken()); // 웜홀의 개수

        
        return bellmanFord();
    }
    
    public static boolean bellmanFord()  throws Exception {
        ArrayList<Edge> edge = new ArrayList<>();
        
        for (int i = 0; i < M + W; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            
            if (i >= M) {
                edge.add(new Edge(S, E, -T)); 
            } else {
                edge.add(new Edge(S, E, T)); 
                edge.add(new Edge(E, S, T)); 
            }
            
        }

        int[] times = new int[N + 1];

        for (int start = 1; start <= N; start++) {
            Arrays.fill(times, INF);
            times[start] = 0;
            boolean ck = false;
            
            for (int i = 1; i <= N; i++) {
                ck = false;
                
                for (int j = 0; j < edge.size(); j++) {
                    Edge cur = edge.get(j);
                    
                    if (times[cur.from] != INF && times[cur.to] > times[cur.from] + cur.time) {
                        times[cur.to] = times[cur.from] + cur.time;
                        ck = true;
                        
                        if (i==N) {
                            return true;
                        }
                    }
                }
                
                if (!ck) {
                    break;
                }
            }
        }
        
        return false;
    }
}

class Edge {
    int from;
    int to;
    int time;

    Edge(int from, int to, int time) {
        this.from = from;
        this.to = to;
        this.time = time;
    }
}

코드 설명

if (!ck) {
    break;
}

위의 코드는 ck = false라면 더 이상 간선이 업데이트될 게 없기 때문에 더 반복문을 돌릴 필요가 없다.

그래서 ck = false라면 반복문을 나가 주는 것이다.

모든 정점을 출발점으로 가정하고 실행하면 시간복잡도가 O(V^2E)이기 때문에, 기존 벨만포드의 시간복잡도 O(VE)보다 더 많은 시간이 소요된다. 해당 문제는 위의 코드를 작성하면 시간 초과가 발생하진 않지만, 2번 방법이 더 올바른 방법일 수 있을 것 같다.

 

 

2번 방법

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
public class Main {
    static BufferedReader br;
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            bw.write(result() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static String result() throws Exception {
        return ckMinusCycle() ? "YES" : "NO";
    }

    public static boolean ckMinusCycle() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken()); //지점의 수
        int M = Integer.parseInt(st.nextToken()); // 도로의 개수
        int W = Integer.parseInt(st.nextToken()); // 웜홀의 개수

        ArrayList<Edge> edge = new ArrayList<>();
        
        for (int i = 0; i < M + W; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            
            if (i >= M) {
                edge.add(new Edge(S, E, -T)); 
            } else {
                edge.add(new Edge(S, E, T)); 
                edge.add(new Edge(E, S, T)); 
            }
            
        }

        int[] times = new int[N + 1];

        boolean ck = false;

        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < edge.size(); j++) {
                Edge cur = edge.get(j);
                
                int time = times[cur.from] + cur.time;
                if (times[cur.to] > time) {
                    times[cur.to] = time;
                    
                    if (i == N) {
                        ck = true;
                    }
                }
            }
        }

        return ck;
    }
}

class Edge {
    int from;
    int to;
    int time;

    Edge(int from, int to, int time) {
        this.from = from;
        this.to = to;
        this.time = time;
    }
}