백준 1865 java - 웜홀(벨만 포드 알고리즘)

문제, 입출력, 테스트케이스

해당 문제는 벨만포드 알고리즘을 사용하는 문제이다. 본인은 벨만 포드 알고리즘을 알고 있지 않아서 약 2시간 30분만의 사투 끝에 구글링을 통해 공부하여서 맞췄다... 맞췄다기 보다 맞춤당했다.

핵심은 음수 사이클 판별하는 알고리즘으로 벨만포드를 사용할 수 있다는 점이다.

 

풀이법은 따로 남기지 않고 동빈나님 강의를 링크로 달아두겠다!

https://www.youtube.com/watch?v=Ppimbaxm8d8 

 

<소스 코드>

package 그래프_DFS;

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.Arrays;
import java.util.StringTokenizer;
 
class Node {
    int to;
    int weight;
 
    Node(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}
 
public class Boj_1865_웜홀 {
    static int N, M, W;
    static int[] dist;
    static ArrayList<ArrayList<Node>> v;
    static final int INF = 99999999;
 
    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;
 
        int TC = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (TC-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
 
            dist = new int[N + 1];
            v = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                v.add(new ArrayList<>());
            }
 
            for (int i = 0; i < M + W; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
 
                if (i < M) { // 도로는 양방향 그래프
                    v.get(start).add(new Node(end, weight));
                    v.get(end).add(new Node(start, weight));
                } else { // 웜홀은 단방향 그래프
                    v.get(start).add(new Node(end, -1 * weight));
                }
            }
 
            boolean chk = false;
            for (int i = 1; i <= N; i++) {
                if (bellmanFord(i)) {
                    chk = true;
                    sb.append("YES\n");
                    break;
                }
            }
 
            if (!chk) {
                sb.append("NO\n");
            }
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 벨만포드 알고리즘
    public static boolean bellmanFord(int start) {
        Arrays.fill(dist, INF);
        dist[start] = 0; // 시작점은 0으로 초기화.
        boolean update = false;
        
        // (정점의 개수 - 1)번 동안 최단거리 초기화 작업을 반복함.
        for (int i = 1; i <= N; i++) {
            update = false;
            
            // 최단거리 초기화.
            for (int j = 1; j <= N; j++) {
            	for (Node road : v.get(j)) {
                    if (dist[j] != INF && dist[road.to] > dist[j] + road.weight) {
                        dist[road.to] = dist[j] + road.weight;
                        update = true;
                    }
                }
            }
            
            if(update && i == N) {
            	return true;
            }else if(!update) {
            	return false;
            }
        }
        return false;
        
    }
 
}