백준 11657번 타임머신 Java

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

문제

---

생각하기

---

• SPFA 알고리즘

• 그래프

• 음수 가중치

동작

결과

코드

---

Java

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static List<List<Edge>> adjList;
    private static final long INF = Long.MAX_VALUE;

    private static class Edge {
        int num;
        int dist;

        private Edge(int num, int dist) {
            this.num = num;
            this.dist = dist;
        }
    } // End of Edge class

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        long[] ret = SPFA();
        if (ret == null) {
            sb.append(-1);
        } else {
            for (int i = 2; i <= N; i++) {
                sb.append(ret[i] == INF ? -1 : ret[i]).append('\n');
            }
        }

        return sb.toString();
    } // End of solve()

    private static long[] SPFA() {
        long[] dists = new long[N + 1];
        Arrays.fill(dists, INF);

        ArrayDeque<Integer> que = new ArrayDeque<>();
        que.offer(1);
        dists[1] = 0;

        boolean[] inQueue = new boolean[N + 1];
        inQueue[1] = true; // 해당 노드가 Queue에 들어가 있는지를 확인
        // 한 정점을 여러번 방문할 수 있으므로 isVisited와는 다르다.

        int[] count = new int[N + 1];
        count[1] = 1;

        while (!que.isEmpty()) {
            int cur = que.poll();
            if (dists[cur] == INF) continue;
            inQueue[cur] = false;

            for (Edge next : adjList.get(cur)) {
                int v = next.num;
                int w = next.dist;

                if (dists[cur] + w < dists[v]) {
                    dists[v] = dists[cur] + w;
                    if (inQueue[v]) continue;

                    que.offer(v);
                    inQueue[v] = true;
                    count[v]++;

                    // 음수 사이클을 방지하기 위해 count배열을 사용
                    if (count[v] >= N) {
                        return null;
                    }
                }
            }
        }

        return dists;
    } // End of SPFA()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            adjList.get(u).add(new Edge(v, d));
        }
    } // End of input()
} // End of Main class