99클럽 코테 스터디 4일차 TIL (챌린저): [백준][Java] 1865 웜홀 - 골드3

 

문제 보기

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

 

 

풀이

나는 벨만 포드 알고리즘이라는 걸 처음 들어봤다.

코테스터디 톡방을 보니 나만 그런 건 아닌 것 같다.

 

그래서 문제를 푸는 것 보다 알고리즘 이해를 하는 데 더 시간이 걸렸다.

 

1. 벨만포드 알고리즘

벨만포드 알고리즘은 가중치가 음수일 수 있는 그래프에서 최단 거리를 찾는 알고리즘이다.

그러나 이 문제에서 할 일은 최단 거리를 찾는 것이 아니다.

주어진 바와 같이 출발 할 때 보다 시간이 과거로 돌아간 경우가 있는 것을 음수의 순환이라 부른다.

 

원래는 노드의 개수 - 1 만큼 모든 간선을 탐색하면 최단거리를 완성할 수 있으나,

음수의 순환이 있을 경우 이후 탐색에서도 최단거리는 계속 작아지고 -INF로 발산한다.

 

두 번째 예제의 그래프를 그렸다.

1->2->3->1으로 돌아오면 -15만큼이나 음으로 돌아가고 말 것이다.

 

1	2	3
0	-3	INF

 

1	2	3
0	-3	-7

 

1	2	3
-15	-6	-7

 

탐색 2회로 모든 검사가 끝났어야 하는데 3회에서 1, 2번 노드의 최단거리가 갱신 됐다.

시작 노드까지 갱신이 됐으니 웃기는 일이다.

 

 

2. 활용 방법

어쨌든 중요한 것은 이 음수의 순환이 있나 찾는 것이다.

  for(int i = 0; i < N; i++) {
    for(int[] edge : edges) {
      if(distance[edge[1]] > distance[edge[0]] + edge[2]) {
        distance[edge[1]] = distance[edge[0]] + edge[2];

        if(i == N - 1) {
          isBack = true;
        }
      }
    }
  }

실제 최단거리를 알아내려고 노력 할 필요는 없다.

그냥 모든 노드만큼 탐색하고도 단축되는 일이 있는가만 찾아내보자.

하나 더 주의 할 점은 모든 노드가 이어져 있다는 보장이 없다는 것으로,

노드의 distance가 INF더라도 그냥 무시해야 한다는 것이다.

 

 

전체 코드

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;

public class Main {
  private static int count = 1;
  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) {
      boolean isBack = false;

      String[] inputs = br.readLine().split(" ");
      int N = Integer.parseInt(inputs[0]);
      int M = Integer.parseInt(inputs[1]);
      int W = Integer.parseInt(inputs[2]);

      List<int[]> edges = new ArrayList<>();

      for(int m = 0; m < M; m++) {
        inputs = br.readLine().split(" ");
        int S = Integer.parseInt(inputs[0]);
        int E = Integer.parseInt(inputs[1]);
        int T = Integer.parseInt(inputs[2]);
        edges.add(new int[]{S, E, T});
        edges.add(new int[]{E, S, T});
      }
      for(int w = 0; w < W; w++) {
        inputs = br.readLine().split(" ");
        int S = Integer.parseInt(inputs[0]);
        int E = Integer.parseInt(inputs[1]);
        int T = Integer.parseInt(inputs[2]);
        edges.add(new int[]{S, E, -T});
      }

      int[] distance = new int[N+1];

      for(int i = 0; i < N; i++) {
        for(int[] edge : edges) {
          if(distance[edge[1]] > distance[edge[0]] + edge[2]) {
            distance[edge[1]] = distance[edge[0]] + edge[2];

            if(i == N - 1) {
              isBack = true;
            }
          }
        }
      }

      bw.write(isBack ? "YES\n" : "NO\n");

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

  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/1865.%E2%80%85%EC%9B%9C%ED%99%80

CodingTest_AutoSave/백준/Gold/1865. 웜홀 at main · MetroDefro/CodingTest_AutoSave