[백준 (Baekjoon)] (java) 문제 11657

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

11404번: 플로이드

1) 접근법

음수를 가지고있는 그래프에서의 최단거리 - Bellman-Ford algorithm

N-1번 만큼 for문을 돌리며 모든 edge를 확인한다.

 

2) 시간 복잡도

O(N^E)

 

3) 이 문제로 얻은 것

- Bellman-Ford 알고리즘 구현법

- Long에 대한 이해 - long에 대해 알고는 있었지만 실제로 사용해야하는 사례는 없었다. 이 문제와 같은 경우 음수 싸이클에 들어갈 때 값이 Integer.MIN_VALUE보다 작아져 에러가 나오는 경우가 있었다. 이 문젠줄도 모르고 20분을 코드와만 씨름했다..

 

4) 코드

import java.io.*;
import java.util.*;

public class p11657 {
    static BufferedReader br;
    static BufferedWriter bw;

    static int N, M;
    static int a,b,c;
    static final long INF = Long.MAX_VALUE;

    static class Path implements Comparable<Path>{
        int end, weight;
        public Path(int end, int weight){
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Path o){
            return weight - o.weight;
        }
    }

    static long[] dist;
    static ArrayList<Path>[] list;
    
    public static void main(String[] args) throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        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];
        Arrays.fill(dist,INF);

        list = new ArrayList[N+1];
        for(int i=1;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        for(int i=1;i<M+1;i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            list[a].add(new Path(b,c));
        }

        StringBuilder sb = new StringBuilder();
        if(bellmanFord()){
            sb.append("-1\n");
        }
        else{
            for (int i = 2; i < N+1; 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();
    }

    private static boolean bellmanFord(){
        dist[1] = 0;
        for(int i=1;i<N;i++){
            for(int j=1;j<N+1;j++){
                for(Path cur:list[j]){
                    if(dist[j]!=INF){
                        if(dist[cur.end]>(dist[j]+cur.weight)){
                            dist[cur.end] = (dist[j]+cur.weight);
                        }
                    }
                }
            }
        }

        for(int i=1;i<N+1;i++){
            for(Path p : list[i]){
                if(dist[i]!=INF && dist[p.end]>(dist[i]+p.weight)) return true;
            }
        }

        return false;
    }
}