[Do It! 코딩테스트 자바편(김종관)] 문제 059(백준 11657번)

로직은 맞는 것 같은데 출력초과가 뜬다면

• 인용 사이트

입력이 다음과 같이 주어지는 경우가 있는 것 같다. N = 500 이고, M = 6000 일 때, 6000개의 간선이 1 → 2 로 -10000 만큼의 비용이 든다. 2 → 1 로 -10000 만큼의 비용이 든다. 이 2개로만 6000개가 채워지는 입력이 있는 것 같다.

위의 경우는 당연하게 음의사이클이 발생함에도, 그 음의사이클의 수치가 int형의 범위를 넘어서서 음의 사이클이 발생하지 않는다고 판단되는 문제가 있어서, 자료형을 long long을 이용해서 구현해주었습니다.

느낀점

• 출력초과 때문에 약간 당황한 문제. static int[] shortestTime; -> static long[] shortestTime;으로 수정

문제

타임머신 (백준: 11657번)

풀이

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

public class Main {
    static ArrayList<Edge> edgeList = new ArrayList<>();
    static long[] shortestTime;
    static int n, m;

    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()); // 도시개수
        m = Integer.parseInt(st.nextToken()); // 버스 노선 개수

        // edgeList 초기화
        for (int i = 1; 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());
            edgeList.add(new Edge(a, b, c));
        }
        // 최단 거리 배열 초기화
        shortestTime = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                shortestTime[i] = 0;
            } else {
                shortestTime[i] = Integer.MAX_VALUE;
            }
        }

        // 에지를 i번 사용할 때
        for (int i = 1; i <= n - 1; i++) {
            // 각 에지에 대해
            for (int j = 0; j < edgeList.size(); j++) {
                Edge now = edgeList.get(j);
                int s = now.start;
                int e = now.end;
                int w = now.value;

                if (shortestTime[s] != Integer.MAX_VALUE && shortestTime[e] > shortestTime[s] + w) {
                    shortestTime[e] = shortestTime[s] + w;
                }
            }
        }

        // 음수 사이클 확인
        boolean isCycle = false;
        for (int j = 0; j < edgeList.size(); j++) {
            Edge now = edgeList.get(j);
            int s = now.start;
            int e = now.end;
            int w = now.value;

            if (shortestTime[s] != Integer.MAX_VALUE && shortestTime[e] > shortestTime[s] + w) {
                isCycle = true;
            }
        }

        // 출력
        if (isCycle) {
            System.out.println(-1);
        } else {
            for (int i = 2; i <= n; i++) {
                if (shortestTime[i] == Integer.MAX_VALUE) {
                    System.out.println(-1);
                } else {
                    System.out.println(shortestTime[i]);
                }
            }
        }
    }
}

class Edge {
    int start;
    int end;
    int value;

    public Edge(int start, int end, int value) {
        this.start = start;
        this.end = end;
        this.value = value;
    }

}