https://www.acmicpc.net/problem/11657

문제이해

다이젝스트라가 아니라 벨만포드인 이유

: 문제의 조건에서 시간 C가 양수가 아닐 때가 있다. 라고 제시함

코드 (1차)

사실 핵심은 이부분이다. 벨만포드는 n-1번 돌고 마지막에 n번째에서는 음수 있으면 사이클이 돌기 때문에 break로 빠져나와야 한다.

// N - 1번 반복
        for (int i = 1; i <= N - 1; i++) {
            for (int u = 1; u <= N; u++) {
                for (Edge edge : graph.get(u)) {
                    int v = edge.to;
                    int w = edge.weight;

                    if (dist[u] != INF && dist[v] > dist[u] + w) {
                        dist[v] = dist[u] + w;
                    }
                }
            }
        }

        // N번째 반복 → 음수 사이클 확인
        for (int u = 1; u <= N; u++) {
            for (Edge edge : graph.get(u)) {
                int v = edge.to;
                int w = edge.weight;

                if (dist[u] != INF && dist[v] > dist[u] + w) {
                    hasCycle = true;
                    break;
                }
            }
        }

        if (hasCycle) {
            System.out.println(-1);
        } else {
            for (int i = 2; i <= N; i++) {
                if (dist[i] == INF) {
                    System.out.println(-1);
                } else {
                    System.out.println(dist[i]);
                }
            }
        }

전체 코드

/*
 * 2025-07-25
 * 문제59 -백준 11657 줄 세우기
 * */
package day8.B11657;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        List<List<Edge>> graph = new ArrayList<>();

        for(int i = 0; i < N; i++){
            graph.add(new ArrayList<>());
        }

        int start = 1;

        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph.get(a).add(new Edge(b, c));
        }

        int dist[] = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // n-1번 돌면서 벨만 포드 조건 확인
        for(int i = 1; i <= N-1; i++){
            for(int j = 1; j <= N; j++){
                for(Edge edge : graph.get(j)){
                    int to = edge.to;
                    int weight = edge.weight;

                    if(dist[j] != Integer.MAX_VALUE && dist[to] > dist[j] + weight){
                        dist[to] = dist[j] + weight;
                    }
                }
            }
        }
        boolean cycle = false;

        // 마지막 n번째거는 음수를 확인한다.
        for(int i = 1; i <= N; i++){
            for(Edge edge : graph.get(i)){
                int to = edge.to;
                int weight = edge.weight;

                if(dist[i] != Integer.MAX_VALUE && dist[to] > dist[i] + weight){
                    cycle=true;
                    break;
                }
            }
        }

        if(cycle){
            System.out.println("-1");
        }else{
            for(int i = 2; i<= N; i++){
                if(dist[i] == Integer.MAX_VALUE){
                    System.out.println("-1");
                }else{
                    System.out.println(dist[i]);
                }
            }
        }
        
        br.close();
    }
}

흠 왜안되지 - 컴파일 에러가 뜬다. 왜?

이번엔 런타임에러

for(int i = 0; i < N; i++){
            graph.add(new ArrayList<>());
        }

이 부분이 문제였다 1번부터 N번까지 쓰니까 i = N일때 문제가 되는 것.

그런데 궁금한건 그럼 i = 1부터 N까지(n 포함) 하게 만들면 되는데 왜 다른 풀이들은 다 i = 0부터 N까지 만들라고 할까?

→ 솔직히 납득안됨