BOJ G3 1865 웜홀 JAVA

1865번: 웜홀

---

문제 읽기

N개의 지점, M개의 도로와 W개의 웜홀(각각 양방향, 단방향)이 연결된 그래프가 주어진다. 도로는 시간 비용이 양수이고, 웜홀은 시간 비용이 음수라고 했으므로, 도로를 양의 가중치, 웜홀을 음의 가중치로 보면 되므로 밸만 포드를 사용하여 해결할 수 있다.

 

다만 문제에서 구하는 것은 최단 거리 그 자체가 아니라, 출발 지점에서 여행을 하고 돌아왔을 때, 시간이 출발 시점보다 더 전으로 가 있을 수 있는지 궁금한 것이다. 이 경우는 음의 가중치 순환 구간이 있는 지를 묻는 것이다.

 

이는 밸만 포드를 사용하면 되며, 자세한 설명은 다음 링크를 참조하면 된다.

Bellman-Ford 알고리즘

---

문제 풀기

밸만 포드를 사용하여 edge를 계속 보며 갱신한다. 그리고 마지막 N번째 반복 때 dist 배열에 변화가 있는 지 확인하여 사이클의 유무를 알 수 있다.

---

실수한 부분

도로는 양방향, 웜홀은 단방향

이 말을 까먹고 도로를 단방향으로 했었다. 양방향으로 해주었다.

2% : 해당 문제의 시작 위치는 1번이 아니다. 모든 지점이 될 수 있다.

처음에 밸만 포드 알고리즘만 생각하다 보니 시작 위치를 당연히 1번 노드라 생각하고 dist[1] = 0으로 초기화 하고 시작했었다. 다시 보니 아니었고.. 임의의 위치에서 시작하게 된다. 그렇기 때문에 딱히 초기화해줄 필요는 없다.

또한,

if (dist[edge.start] == INF) continue;

 

위 구문도 필요 없다.

 

해당 구문의 의미는 ‘시작 위치와 연결되어 있지 않는 노드로는 가지 않는다’는 것인데, 이 문제에서는 여행의 시작 점은 모든 지점이 될 수 있고, 연결 그래프라는 보장이 없기 때문에 해당 구분은 삭제해야 한다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_1865_웜홀 {
    static class Edge{
        int start, end;
        int cost;
        public Edge(int start, int end, int cost){
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
    static int N, M, W;
    static List<Edge> edges;
    static long[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while(T-- > 0){
            StringTokenizer st = new StringTokenizer(in.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            edges = new ArrayList<>();
            dist = new long[N+1];
            for (int i = 0; i < M; i++){
                st = new StringTokenizer(in.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, cost));
                edges.add(new Edge(end, start, cost));
            }

            for (int i = M; i < M+W; i++){
                st = new StringTokenizer(in.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, (-1) * cost));
            }

            sb.append((bellmanFord())? "YES" : "NO").append("\\n");
        }
        System.out.println(sb);
    }

    static long INF = Long.MAX_VALUE - 100001;

    private static boolean bellmanFord() {
        Arrays.fill(dist, INF);
//        dist[1] = 0;

        boolean isCycle = false;
        for (int i = 0; i < N; i++){
            for (Edge edge : edges){
//                if (dist[edge.start] == INF) continue;

                if (dist[edge.end] > dist[edge.start] + edge.cost){
                    if (i == N-1) isCycle = true;
                    dist[edge.end] = dist[edge.start] + edge.cost;
                }
            }
        }
        return isCycle;
    }
}