[백준] 1865 웜홀 - Graph Theory / Java

• 문제 링크

1865번: 웜홀

 

• 풀이 과정

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

위의 문제와 유사한 벨만 포드 알고리즘 문제이다.

 

다만 이 문제에선 테스트 케이스가 여러 개 주어지고,

간선의 개수 m 과 음의 가중치 간선의 개수 w 가 주어지며 m 은 무향 그래프로 입력받아 저장한다.

 

또한 문제에서 특정 시작점을 명시하지 않았고,

어떤 노드에서 시작을 하더라도 음의 사이클의 존재 유무만 파악하면 되므로

최단 거리를 구할 때 사용하는 inf 값을 생성하지도, 비교하지도 않는다.

따라서 dist 배열 또한 0으로 초기화해도 무방하다.

 

이렇게 n 번째 순회에서 음의 사이클의 존재 유무를 파악하여

반환한 boolean 값에 따라 "YES" 또는 "NO" 를 정답으로써 출력한다.

 

• 풀이 코드

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, w;
    static int[] dist;
    static List<Edge> list;

    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());
        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];
            list = new ArrayList<>();

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

                if (i < m) {
                    list.add(new Edge(src, dest, weight));
                    list.add(new Edge(dest, src, weight));
                } else
                    list.add(new Edge(src, dest, weight * -1));
            }

            bw.write((bellmanFord() ? "YES" : "NO") + "\n");
        }

        bw.flush();
    }

    private static boolean bellmanFord() {
        for (int i = 1; i <= n; i++) {
            for (Edge edge : list) {
                if (dist[edge.dest] > dist[edge.src] + edge.weight) {
                    dist[edge.dest] = dist[edge.src] + edge.weight;

                    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;
        }
    }

}