글 읽기 - 출력초과 문제 해결이 되었는데 이유를 모르겠습니다

zzz0484 3년 전 3

dist배열을 int배열로 선언했다가 long배열로 바꿔주니까

출력 초과 문제가 해결되었습니다.

근데 왜 dist를 long타입 배열로 해야하는지 잘 모르겠습니다

INF가 50000이고 기존 dist값이 INF라면 갱신을 따로 하지 않는데 long 범위의 값이 들어갈 일이 있나요?

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static class Road {
        int start, end, cost;

        public Road(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

    private static int INF = 500 * 10_000;
    static int n, m;
    static Road[] roads;
    static long[] dist;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dist = new long[n + 1];
        roads = new Road[m];
        Arrays.fill(dist, INF);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            roads[i] = new Road(start, end, cost);
        }

        StringBuilder sb = new StringBuilder();

        if (!bellmanFord()) { //음의 cycle이 없는 경우
            for (int i = 2; i <= n; i++) {
                sb.append(dist[i] == INF ? "-1\n" : dist[i] + "\n"); //해당도시로 가는 경로가 없다면 -1, 있다면 최소 경로 출력
            }
        } else sb.append("-1\n");
        //음의 cycle이 있는 경우(1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면) -1 출력

        bw.write(sb.toString());
        bw.close();
    }

    static boolean bellmanFord() {
        dist[1] = 0;
        boolean isUpdate = false; //음의 cycle 여부 - 음의 cycle이 있다면 true, 없다면 false 리턴

        // N-1 Edge Relaxation
        for (int i = 1; i <= n; i++) {
            isUpdate = false;

            for (Road road : roads) { // edge개수 만큼 확인을 한다.
                if (dist[road.start] == INF) continue;
                if (dist[road.end] > dist[road.start] + road.cost) {
                    dist[road.end] = dist[road.start] + road.cost;

                    // Negative Cycle
                    if (i == n) {
                        isUpdate = true;
                        break loop1;
                    }
                }
            }
        }
        return isUpdate;
    }
}

kangwlgns 3년 전 47

이 문제에서 출력 초과가 발생하는 이유는 -1을 출력해야 하는 상황에서 각 도시로 가는 최단 거리들을 출력하기 때문입니다.

질문하신 내용처럼 기존 dist에 들어있는 INF가 초과되어 overflow가 발생하지는 않으나, 이 문제는 가중치가 음수인 것이 허용되는 벨만-포드 알고리즘 문제입니다. 음수 사이클이 존재한다면 끝 없이 최소값이 갱신될 수 있고 이 때문에 출력초과가 발생하는 것입니다.

왜 이 때문에 출력초과가 발생하느냐? 가 궁금하실텐데 결론부터 말하자면 underflow때문입니다. 문제에서 주어진 조건인 정점의 개수가 500개, 간선의 개수가 6000개, 최소 가중치가 -10000이라면 충분히 underflow가 발생할 수 있는 수치입니다. (-500 * 6000 * 10000 = -3 * 10^10, Integer.MIN_VALUE = 약 -2*10^9)

우선 -1을 출력하는 조건은 '정점의 개수를 V라 할 때, V - 1번 만큼 최소값을 충분히 갱신해주고 V번째에서 최소값이 갱신 되는 경우' 입니다.

그리고 이런 경우가 있다고 가정해봅시다.

- 정점 V: 500개 (1에서 출발)

- 간선 E: 6000개 (1에서 2로 가며 가중치는 -10000, 2에서 1로가며 가중치는 -10000 ...반복 ...)

벨만-포드 알고리즘에서의 내부 반복문이 1번 회전한다면 2로 가는 비용은 -10000로 갱신, 3번 회전한다면 2로 가는 비용은 -30000으로 갱신됩니다. 이런 과정을 거쳐서 외부 반복문이 한 번 회전한다면 2로 가는 비용은 -60000000로 갱신됩니다. 한번의 회전으로 이미 충분히 낮은 숫자가 됐다고 직감하실 수 있을 겁니다. 위의 경우을 실제로 돌려보니 V = 466만 해도 이미 언더플로우가 나버려서 최소값 갱신이 불가능합니다. 즉, dist를 long으로 설정해줘야 정상적인 음의 값으로 갱신할 수 있기 때문에 벨만-포드 알고리즘에서 음수 사이클이 존재한다고 판정할 수 있는 것입니다.

i5533m 3년 전 1

dist long long으로 바꾸십쎠

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

출력초과 문제 해결이 되었는데 이유를 모르겠습니다

zzz0484 3년 전 3

kangwlgns 3년 전 47

i5533m 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말