[백준] 11657 타임머신 - Graph Theory / Java

• 문제 링크

11657번: 타임머신

 

• 풀이 과정

한 노드(1번 도시)에서 다른 모든 노드(나머지 도시)까지의 최단 거리(최단 시간)를 구하고

타임머신이라는 간선의 가중치가 음수인 경우가 존재하므로 Bellman-Ford 알고리즘을 활용한다.

 

각 노드의 최단 거리를 dist 배열에 무한대 값(inf) 으로 초기화하고,

각 간선의 출발, 도착점, 가중치의 정보를 Edge 객체로 저장한다.

 

1번 노드를 출발 노드로 나머지 노드들의 최단 거리를 갱신하고

음의 사이클 존재 여부를 반환하는 bellmanFord 함수를 실행한다.

 

노드의 개수 n 회만큼 모든 간선을 탐색하며

간선의 출발점까지의 최단 거리가 inf 가 아니고,(dist[s] != inf)

도착점의 누적된 최단 거리가, 출발점 최단 거리와 현재 간선의 가중치의 합보다 클 경우,(dist[d] > dist[s] + w)

도착점의 최단 거리를 작은 최단 거리값으로 갱신한다.(dist[d] = dist[s] + w)

 

이때 n 번째 순회에서 값의 갱신이 이루어진다면 음의 사이클이 존재하므로 true 를 반환, -1 을 출력한다.

 

false 를 반환하여 음의 사이클이 존재하지 않는다면

2 ~ n 의 모든 노드까지의 최단 거리를 정답으로써 출력하고

만약 값의 갱신이 없었다면 해당 노드로 가는 경로가 없으므로 -1 을 출력한다.

 

• 풀이 코드

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

public class Main {

    static int n, m;
    static long[] dist;
    static List<Edge> list;
    static int inf = Integer.MAX_VALUE;

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

        for (int i = 1; i <= n; i++)
            dist[i] = inf;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list.add(new Edge(src, dest, weight));
        }

        if (bellmanFord(1))
            bw.write(-1 + "\n");
        else {
            for (int i = 2; i <= n; i++) {
                if (dist[i] == inf)
                    bw.write(-1 + "\n");
                else
                    bw.write(dist[i] + "\n");
            }
        }

        bw.flush();
    }

    private static boolean bellmanFord(int root) {
        dist[root] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                int s = list.get(j).src;
                int d = list.get(j).dest;
                int w = list.get(j).weight;

                if (dist[s] != inf && dist[d] > dist[s] + w) {
                    dist[d] = dist[s] + w;

                    if (i == n)
                        return true;
                }
            }
        }

        return false;
    }

    private static class Edge {
        int src, dest, weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

}