[Algorithm/Java][백준] 1865 웜홀

[BOJ] 1865 웜홀

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

문제 접근

벨만 포드 알고리즘은 다음과 같다.
1.시작 노드를 설정한다.
2.최단 경로 테이블(배열)을 초기화한다.
3.(정점의 개수-1)번동안 모든 간선을 탐색하여 최단 경로 테이블을 갱신한다.
여기서 음의 순환이 발생하는지 알고싶다면 한번 더 모든 간선에 대해서 탐색을 하고 이때, 최단 경로 테이블이 갱신이 된다면 음의 순환이 발생한 것이다.
이 문제는 모든 노드를 시작 노드를 설정할 필요가 없이 음의 순환이 있는지 없는지만 체크하면 되기때문에 1번 노드에 대해서만 벨만 포드 알고리즘을 수행하고 이때, 음의 순환이 발생하는지 아닌지를 검사하였다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1865 {
    static ArrayList<ArrayList<Node>> list;
    static int[] dist;
    static String answer;
    static int n;
    static private final int INF = 987654321;
    static class Node {
        int to;
        int time;
        Node(int to, int time){
            this.to = to;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            n = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list = new ArrayList<>();
            for(int i =0 ;i<=n; i++){
                list.add(new ArrayList<>());
            }
            //== 입력 받기 ==//
            for(int i = 1; i<=v+w; i++){
                st = new StringTokenizer(br.readLine()," ");
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                if(i <= v){
                    list.get(s).add(new Node(e,t));
                    list.get(e).add(new Node(s,t));
                } else {
                    list.get(s).add(new Node(e,t*-1));
                }
            }
            //== 벨만 포드 알고리즘 수행==//
            dist = new int[n+1];
            answer = bellman_ford() ? "YES":"NO";
            sb.append(answer+"\n");
        }
        System.out.print(sb.toString());
    }
    //==벨만-포드 알고리즘==//
    public static boolean bellman_ford(){
        //배열 초기화
        Arrays.fill(dist,INF);
        //시작 지점 초기화
        dist[1] = 0; 
        boolean update = false;
        // n-1번까지
        for(int i =1; i< n; i++){
            update = false;
            //== 최단거리 초기화==//
            for(int j =1; j<= n; j++){
                for(Node n: list.get(j)){
                    if(dist[n.to]>dist[j] + n.time){
                        dist[n.to] = dist[j] + n.time;
                        update = true;
                    }
                }
            }
            // 더이상 업데이트가 안되면 break;
            if(!update) break;
        }
        //n번까지 촤단경로 업데이트가 이루어진다면
        //음의 사이클이 존재하는것이라고 판단한다.
        if(update) {
            for (int i = 1; i <= n; i++) {
                for (Node n : list.get(i)) {
                    // 이때 거리가 줄어든다면, 음의 순환이 이루어지고 있는것이다.
                    if (dist[n.to] > dist[i] + n.time) {
                        return true;
                    }

                }
            }
        }
        return false;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

17번 제출만에 성공했다.. 사실 다른 블로그를 조금 참조했다...다 풀고나니까 벨만포드 알고리즘이 이해가 되었다.
그리고 오류가 났던 포인트는
내가 벨만포드를 잘 이해 못한 것
a -> b로 가는 간선이 하나가 아닐 수도 있다는것
도로는 양방향이라는 것
사실 2번째것만 신경쓰면 된다. 3번째는 내가 문제를 대충 읽었고, 벨만 포드는...음...
골드3이라서 역시 어려웠다...