P.1865 웜홀 [추가]

2022.07.16 - [코딩테스트_JAVA/백준] - P.1865 웜홀

P.1865 웜홀

 

 

코드

package Baekjoon.Review;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class P_1865 {

    static int n;
    static ArrayList<Node>[] graph;
    static int[] dist;

    static class Node {
        int edge;
        int weigh;

        public Node(int edge, int weigh) {
            this.edge = edge;
            this.weigh = weigh;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            n = line[0]; int  m = line[1], w = line[2];
            graph = new ArrayList[n + 1];
            for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
            for (int i = 0; i < m + w; i++) {
                line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

                if (i < m) {
                    graph[line[0]].add(new Node(line[1], line[2]));
                    graph[line[1]].add(new Node(line[0], line[2]));
                }
                else
                    graph[line[0]].add(new Node(line[1], -line[2]));
            }

            dist = new int[n + 1];
            if (bellmanFord()) bw.write("YES\n");
            else bw.write("NO\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }

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

        for (int i = 0; i < n; i++) {
            boolean update = false;
            for (int j = 1; j <= n; j++) {
                for (Node node : graph[j]) {
                    if (dist[node.edge] > dist[j] + node.weigh) {
                        dist[node.edge] = dist[j] + node.weigh;
                        update = true;
                        if (i == n - 1) return true;
                    }
                }
            }

            if (!update) break;
        }

        return false;
    }
}

코드 설명

해당 문제를 복습하면서 벨만-포드 알고리즘도 다시 공부하고 이전 코드에서 보완해야할 점을 보완했다.

 

먼저, 이전의 코드는 n개의 정점만큼 벨만포드를 돌아보며 해당 정점을 시작점으로 잡고 음의 가중치 순환이 있는지 확인했다.

이 문제는 시작 정점을 정해주지 않았으므로 모든 정점에 대해서 돌아보는 것이 정석의 풀이인 것은 맞다.

하지만 시작 정점이 어떤 것이든 상관없이 그래프 자체에 음의 순환이 존재하고, 한 번의 벨만-포드로 이를 검증해낼 수 있다면 시간복잡도를 훨씬 더 줄일 수 있을 것이다.

 

이전 코드와 크게 다른 점은 INF 검증을 제외했다는 것이다.

만약 INF 검증을 하게 된다면 한 번의 벨만-포드를 사용하면서 1번 노드를 강제로 시작 정점으로 잡았으므로 이와 이어지지 않은 다른 서브 그래프에서 음의 순환이 일어난다면 틀린 답을 도출해내게 된다.

// INF를 검사하는 이전 코드

if (dist[j] == Integer.MAX_VALUE || nextWeigh == Integer.MAX_VALUE) continue;

if (dist[next] > dist[j] + nextWeigh) {
    dist[next] = dist[j] + nextWeigh;
    isUpdated = true;
    if (i == n - 1) return true;
}

 

또 다른 차이점은 INF를 Integer의 무한으로 가정한 것이 아닌 특정한 수로 가정했다는 것이다.

위 코드의 경우 5000000로 설정되어 있는데 이는 정점의 최대 개수가 500개이고, 정점 간 시간의 최댓값이 10000이기 때문이다.

Integer의 무한으로 가정할 경우 음의 순환이 일어났을 때 오버플로우 방지가 되지 않는다.

즉, -2147483648에서 -1이 될 경우 2147483647이 되니 update가 true로 바뀌지 않게 된다.

 

이전 코드와 현재 코드의 시간 결과 차이는 300ms 정도로 고생한 거에 비해 많이 차이가 나진 않는다 🫥