[백준] 11657 타임머신

1. 문제

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

11657번: 타임머신

2. 접근방법

밸만포드 알고리즘 쓰면 쉽게 풀리는 문제

 

3중 포문으로 가능한 업데이트 방법을 다해보는 알고리즘이다.

각 노드에서 가능한 업데이트 방법은 무조건 N-1번 인데

 

그 이상 업데이트를 했을 때 값 변화가 있으면

무한히 - 가 되는 순환이 있는 것을 알아 낼 수 있다.

 

밸만 포드에 대해 자세한 내용은 구글링을 해보자

3. 자바 코드

package backjoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class P11657타임머신밸만 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Point> arr[] = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) arr[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            arr[Integer.parseInt(st.nextToken())].add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        long[] dist = new long[N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dist[j] == Long.MAX_VALUE)
                    continue;
                for (Point k : arr[j]) {
                    if (dist[k.x] > dist[j] + k.y) {
                        dist[k.x] = dist[j] + k.y;
                        if(i == N-1){
                            System.out.println(-1);
                            return;
                        }
                    }
                }
            }
        }
        for (int i = 2; i <= N; i++)
            System.out.println(dist[i] == Long.MAX_VALUE ? -1 : dist[i]);
    }
}

4. 마치며

처음에 밸만 포드 말고 다른 방법으로 풀어 보려고 삽질하다가

그냥 밸만 포드가 정답임을 인정하고 포기했다....

하나의 알고리즘에 딱 맞는 문제 싫어..