[백준] 11657: 교환 - JAVA

in Algorithm on 그래프 이론

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

풀이

도시마다 연결된 줄이 있고, 줄마다 가중치가 있다.

가중치에는 음수값도 있어서 1번도시에서 어떤 도시로 가는 과정에서 무한히 오래 전으로 돌릴 수 있으면 -1을 출력해야한다.

그렇지 않다면 2번~n번 도시까지 가는 가장 빠른 시간을 출력한다.

음수 가중치가 있기 때문에 벨만포드 알고리즘을 사용하는 문제였다.

벨만포드 알고리즘에서는 우선 ‘정점의 개수 - 1’만큼 루프를 돈다.

먼저 정점의 사이즈만큼 dist 배열을 만들어 출발지를 0으로 설정하고 나머지 값은 INF로 설정한다.

‘정점의 개수 - 1’만큼 루프를 돌면서 dist의 값이 INF가 아닌 정점에 대해 연결 된 정점까지 걸리는 cost를 최솟값으로 갱신한다.

‘정점의 개수 - 1’만큼 루프를 돌았다면, 한번 더 루프를 도는데, 이때 갱신되는 값이 있다면 문제에서 말하는 ‘무한히 오래 전으로 돌릴 수 있는’ 상황이 발생한 것이다.

메모리: 27188KB

시간: 304ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int v;
        int cost;

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    static int n, m;
    static ArrayList<ArrayList<Node>> list;
    static long[] 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());

        list = new ArrayList<>();
        dist = new long[n + 1];
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
            dist[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; 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());
            list.get(a).add(new Node(b, c));
        }

        boolean flag = bellmanFord();

        StringBuilder sb = new StringBuilder();
        if (flag) {
            for (int i = 2; i <= n; i++) {
                if (dist[i] == Integer.MAX_VALUE) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(dist[i]).append("\n");
                }
            }
        } else {
            sb.append(-1).append("\n");
        }

        System.out.println(sb);
    }

    private static boolean bellmanFord() {
        dist[1] = 0;
        boolean flag = false;

        for (int i = 0; i < n - 1; i++) {
            flag = false;

            for (int j = 1; j <= n; j++) {
                for (Node node : list.get(j)) {
                    if (dist[j] == Integer.MAX_VALUE) {
                        break;
                    }

                    if (dist[node.v] > dist[j] + node.cost) {
                        dist[node.v] = dist[j] + node.cost;
                        flag = true;
                    }
                }
            }

            if (!flag) {
                break;
            }
        }

        if (flag) {
            for (int i = 1; i <= n; i++) {
                for (Node node : list.get(i)) {
                    if (dist[i] == Integer.MAX_VALUE) {
                        break;
                    }

                    if (dist[node.v] > dist[i] + node.cost) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

}