1. 문제 설명 📌

문제 링크

벨만 포드 알고리즘 공부하고 한 번 써보라는 견본 문제이다.
주어지는 간선 정보는 모두 단방향이다.

2. 구현 방법 🗃️

KEY WORD: BELLMAN-FORD ALGORITHM

0️⃣ <출발지, 도착지, 간선 가중치> 형태로 모든 간선을 저장, 최소 비용 배열인 dist [] 선언.
(N: 정점의 수, M: 간선의 수, dist 배열은 Long.MAX_VALUE로 초기화)
1️⃣ 출발지를 1로 설정하고, N-1만큼 모든 간선을 돌면서 다음 구문을 실행한다.
- 1️⃣-1) 현재 조회중인 간선의 출발지를 A, 도착지를 B, A➜B의 가중치를 C라고 할 때,
  dist[A] != ∞︎︎ && dist[B] > dist[A] + C이면, dist[B] = dist[A] + C로 최신화 해준다.
2️⃣ 위 과정을 끝낸 후, 벨만 포드 내의 음수 사이클이 있는지 확인한다. (음수 사이클이 있으면 벨만 포드 무소용)
1회 1️⃣-1)을 한 번 반복한다. 만약 이후, dist[]의 값이 하나라도 바뀌었다면 음수 사이클이 존재한다는 것이다.
(만약 음수 사이클이 존재하면, -1 출력 후 프로그램을 종료한다.)
3️⃣모든 dist 배열의 원소를 한 줄씩 출력한다. (아직 Long.MAX_VALUE인 경우, 출발점에서 닿을 수 없는 정점이란 뜻 이므로, -1로 변환해 출력한다.)

(1) 시간복잡도 분석 🕓

간선 리스트 초기화 : $O(M)$
벨만포드 알고리즘 $O(NM)$
출력: $O(M)$

결론 : $O(NM)$

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder ans = new StringBuilder();
    static int N, M;
    static int [] a, b;
    static long [ ] c, dist;
    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());

        dist = new long [N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        a = new int [M]; b = new int [M]; c = new long [M];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end   = Integer.parseInt(st.nextToken());
            long weight =  Long.parseLong(st.nextToken());
            a[i] = start; b[i] = end; c[i] = weight;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                int start   = a[j];
                int end     = b[j];
                long weight  = c[j];
                if(dist[start] != Long.MAX_VALUE){
                    dist[end] = Math.min(dist[end], dist[start] + weight);
                }
            }
        }

        for (int i = 0; i < M; i++) {
            int start   = a[i];
            int end     = b[i];
            long weight  = c[i];
            long oldValue = dist[end];

            if(dist[start] != Long.MAX_VALUE){
                dist[end] = Math.min(dist[end], dist[start] + weight);
            }

            if(oldValue != dist[end]){
                System.out.println(-1);
                return;
            }
        }

        if (N == 1) {
            System.out.println(dist[1]);
            return;
        }

        for (int i = 2; i <= N; i++) {
            ans.append(dist[i] == Long.MAX_VALUE? -1 : dist[i]).append("\n");
        }
        System.out.println(ans);
    }
}

4. 배운 것들 🎯

(1) 출력 초과가 났던 이유

처음에 dist 배열을 int 형태로 두고 Integer.MAX_VALUE로 계산했더니 출력 초과가 났다. 모든 간선이 -10,000 이고 정점의 개수가 50개 , 노선의 개수가 6000개인 경우를 생각해보자. 최악의 경우, dist 배열의 원소로 -30억이 들어갈 수 있다. 이것은 언더플로우를 일으켜 출력 초과를 야기한다.