[JAVA] BOJ 백준 1865번 - 웜홀

 

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1865번: 웜홀

---

2. 내가 푼 방법

그래프 문제에서 음수 가중치를 가지고, 사이클이 존재하고, 최단 경로를 확인해야 할 경우에는 벨만포드 알고리즘을 이용해야 한다. 매번 모든 간선을 확인함으로써 사이클이 발생하는지 알 수 있기 때문에, O(V+E)의 시간복잡도를 가진다.

 

최단 경로가 갱신됨을 확인해야 하므로 Integer.MAX_VALUE 값을 가지는 dist 변수를 세팅해준다.

그 후 현재 노드(s)가 음수 사이클을 가지는지 확인하기 위해 N-1번 for문을 돌면서 각 노드의 모든 간선을 확인해준다.

만약 N-1번 동안 계속 변화했다면, 최종 N번이 됐을 때의 변화를 확인하면서 음수 사이클을 알 수 있다.

public static boolean bellmanford(int s) {
    int[] dist = new int[N+1];
    Arrays.fill(dist, Integer.MAX_VALUE);

    dist[s] = 0;

    boolean isChange = false;
    for (int n = 1; n < N; n++) {
        isChange = false;

        for (int i = 1; i <= N; i++) {
            for (Tuple t : list[i]) {
                int v = t.v;
                int w = t.w;

                if (dist[i] != Integer.MAX_VALUE && dist[v] > dist[i] + w) {
                    dist[v] = dist[i] + w;
                    isChange = true;
                }
            }
        }

        if (!isChange) break;
    }

    if (isChange) {
        for (int i = 1; i <= N; i++) {
            for (Tuple t : list[i]) {
                int v = t.v;
                int w = t.w;

                // 갱신됨
                if (dist[i] != Integer.MAX_VALUE && dist[v] > dist[i] + w) {
                    return true;
                }
            }
        }
    }

    return false;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1865.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static List<Tuple>[] 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));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            list = new ArrayList[N+1];
            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                list[a].add(new Tuple(b, w));
                list[b].add(new Tuple(a, w));
            }
            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                list[a].add(new Tuple(b, (-1) * w));
            }

            boolean canMinus = false;
            for (int i = 1; i <= N; i++) {
                if (bellmanford(i)) {
                    canMinus = true;
                    break;
                }
            }

            if (canMinus) bw.write("YES"+"\n");
            else bw.write("NO"+"\n");
        }

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

    public static boolean bellmanford(int s) {
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[s] = 0;

        boolean isChange = false;
        for (int n = 1; n < N; n++) {
            isChange = false;

            for (int i = 1; i <= N; i++) {
                for (Tuple t : list[i]) {
                    int v = t.v;
                    int w = t.w;

                    if (dist[i] != Integer.MAX_VALUE && dist[v] > dist[i] + w) {
                        dist[v] = dist[i] + w;
                        isChange = true;
                    }
                }
            }

            if (!isChange) break;
        }

        if (isChange) {
            for (int i = 1; i <= N; i++) {
                for (Tuple t : list[i]) {
                    int v = t.v;
                    int w = t.w;

                    // 갱신됨
                    if (dist[i] != Integer.MAX_VALUE && dist[v] > dist[i] + w) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public static class Tuple {
        int v;
        int w;

        public Tuple(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
}

---

4. 결과 및 회고

그래프 문제는 꾸준히 풀어왔는데 벨만포드 알고리즘과 크루스칼 알고리즘을 바로 떠올리지 못하는 것 같다.

다른 그래프 알고리즘 풀이를 시도하다가 생각해내서,, 이 유형들을 더 풀어봐야겠다.