[백준] 1865. 웜홀 (Java)

 

1865번: 웜홀

풀이

벨만-포드 알고리즘을 몰라서 구글링하며 풀이ㅠ
알고리즘 이해에 참고한 글 👍🏻👍🏻👍🏻
코드 작성에 참고한 글

벨만포드 알고리즘이란?

• 최단 경로를 찾는 알고리즘 중 하나
• 가중치가 음수일 경우 다익스트라 알고리즘을 사용하면 무한 루프에 빠지게 된다.
• 따라서 음수 가중치를 다룰 수 있는 벨만-포드 알고리즘을 사용해야 한다.
• 간단한 원리는 다음과 같다.
  • 노드 수를 V라 하면 시작점에 대해 최대 연결된 간선 개수는 V-1개이다.
  • 시작점을 기준으로 V-1번 탐색하면 최단경로를 갱신할 수 있다. (이를 edge relaxation이라 부름)
  • 하지만 그래프 내에 값이 점점 작아지는 음수 사이클이 존재할 수 있다.
  • 이제 마지막으로 한번 더 최단경로를 갱신하는 작업을 할 때 만약 값의 업데이트가 일어난다면 음수사이클이 존재한다는 뜻이다.
• 원래라면 음수 사이클이 존재하면 안되지만, 여기선 음수 사이클이 존재하는 그래프가 정답이다.

---

• 더이상 edge relaxation이 일어나지 않을 경우 for loop를 끝내는 변수를 추가해줘도 좋다.

문제풀며 생긴 의문점

시작점은 어디?

• 시작점이 주어지지 않아 1을 그냥 시작점으로 두었다.
• 찾아보니 모든 정점을 시작점으로 두고 업데이트해도 되는데 이때 INF를 같이 체크하는 것 같다.

인접행렬 말고 인접리스트로 할 땐 웜홀 위치 및 값을 어떻게 갱신하는지?

• 찾아보니 사람들은 그냥 기존의 정점에 음수 값을 추가했다.
• 어차피 해당 ArrayList 내의 모든 노드를 조회하기 때문에 값이 업데이트 되어 그런 듯 하다. (신기한 접근방법인듯)

---

코드

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

public class Main {
    static int TC, N, M, W;
    static int[][] adj;
    static int[] dist;
    static final int INF = 2500 * 10001;

    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;

        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];
            Arrays.fill(dist, INF);
            dist[0] = dist[1] = 0;
            adj = new int[N + 1][N + 1];

            for (int i = 1; i <= N; i++)
            Arrays.fill(adj[i], INF);

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                adj[from][to] = Math.min(adj[from][to], d);
                adj[to][from] = adj[from][to];
            }

            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());

                adj[from][to] = -d;
            }

            if (BellmanFord()) bw.write("YES\n");
            else bw.write("NO\n");
        }
        br.close();
        bw.close();
    }

    public static boolean BellmanFord() {
        // 1을 무조건 시작지점으로
        // |N-1|번 edge relaxation 수행
        // 더이상 업데이트가 일어나지 않으면 for loop를 끝내도 된다.
        boolean updated = false;
        for (int n = 0; n < N - 1; n++) {
            updated = false;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dist[i] + adj[i][j] < dist[j]) {
                        dist[j] = dist[i] + adj[i][j];
                        updated = true;
                    }
                }
            }
            if (!updated) break;
        }

        if (updated) {
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    if (dist[i] + adj[i][j] < dist[j]) return true;
        }

        return false;
    }
}