[BOJ] 백준 11657번 : 타임머신 (JAVA)

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

 

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

 

 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

 

풀이

1865번 웜홀 문제와 상당히 유사한 문제였습니다. 혹시 아직 웜홀 문제를 풀지 않으신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 1865번 : 웜홀 (JAVA)

 

 

웜홀 문제와 마찬가지로 이 문제도 '벨만 포드 알고리즘'을 사용합니다.

그리고 출력하는 과정에서 음의 사이클이 발생할 경우 -1을 1번 출력하고, 그렇기 않을 경우 최단거리 배열에 값을 출력하면 됩니다. 다만, 최단거리 배열에 INF가 들어가 있을 경우 INF 대신 -1을 출력해야 합니다.

 

반환형이 boolean 타입인 벨만 포드 알고리즘을 구현하여, 메인 함수에서 벨만 포드 알고리즘의 반환값이 true인 경우, 음의 사이클이 발생했다고 판단하여 -1을 1번만 출력하고, 그렇지 않을 경우 최단거리 배열의 값에 따라 적절히 출력하면 됩니다.

 

이렇게 생각을 하고 제출을 하였으나, 40%쯤에서 출력 초과가 발생하였습니다.

왜 이러한 현상이 발생했는지 문제의 조건을 체크해 보니, 오버플로우가 발생할 수 있겠다는 생각이 들었습니다.

 

문제에서 N은 최대 500, M은 최대 6000, C는 최소 -10,000 인데 아래와 같이 예시를 봅시다.

 

N = 500, M = 6000

1 -> 2 : -10,000

2 -> 1 : -10,000

 

극단적으로 위 2개만으로 입력값이 6000개가 주어진 경우, dist 배열을 int 타입으로 설정하면 오버플로우가 발생하게 되어 음의 사이클이 발생하지 않았다고 판단하게 될 수 있습니다.

 

따라서 dist 배열의 자료형을 int가 아닌 long으로 설정해야 출력 초과가 발생하지 않고, 정상적으로 정답 처리가 될 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class City {
    int end;
    int weight;
 
    City(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
}
 
public class Main {
    static int N, M;
    static ArrayList<ArrayList<City>> a;
    static long[] dist; // 자료형을 int로 할 경우 오버플로우 발생함.
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken()); // 도시의 개수
        M = Integer.parseInt(st.nextToken()); // 버스 노선의 개수
 
        a = new ArrayList<>(); // 인접 리스트
        dist = new long[N + 1]; // 최단거리 배열
 
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
            dist[i] = INF;
        }
 
        // 단방향 인접리스트 구현
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
 
            a.get(A).add(new City(B, C));
        }
 
        StringBuilder sb = new StringBuilder();
        if (bellmanFord()) {
            sb.append("-1\n");
        } else {
            for (int i = 2; i <= N; i++) {
                if (dist[i] == INF) {
                    sb.append("-1\n");
                } else {
                    sb.append(dist[i] + "\n");
                }
            }
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static boolean bellmanFord() {
        dist[1] = 0; // 시작점은 0으로 초기화.
        boolean update = false;
 
        // (정점의 개수 - 1)번 동안 최단거리 초기화 작업을 반복함.
        for (int i = 1; i < N; i++) {
            update = false;
 
            // 최단거리 초기화.
            for (int j = 1; j <= N; j++) {
                for (City city : a.get(j)) {
                    if (dist[j] == INF) {
                        break;
                    }
 
                    if (dist[city.end] > dist[j] + city.weight) {
                        dist[city.end] = dist[j] + city.weight;
                        update = true;
                    }
                }
            }
 
            // 더 이상 최단거리 초기화가 일어나지 않았을 경우 반복문을 종료.
            if (!update) {
                break;
            }
        }
 
        // (정점의 개수 - 1)번까지 계속 업데이트가 발생했을 경우
        // (정점의 개수)번도 업데이트 발생하면 음수 사이클이 일어난 것을 의미함.
        if (update) {
            for (int i = 1; i <= N; i++) {
                for (City city : a.get(i)) {
                    if (dist[i] == INF) {
                        break;
                    }
 
                    if (dist[city.end] > dist[i] + city.weight) {
                        return true;
                    }
                }
            }
        }
 
        return false;
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.