[백준]11657. 타임머신

📄 링크

타임머신

---

💡 문제 분석

음의 가중치를 가질 수 있는 최소 비용 문제입니다.
음의 가중치를 가지고 있는지 판단할 수 있는 벨만-포드 알고리즘을 사용 해야겠다고 생각했습니다.
V - 1번을 완화작업을 하면 모든 정점의 최소 비용을 알 수 있습니다. 그리고 V번째 완화 작업을 했을 때 실패하지 않고 성공한다면 음수 간선이 존재하는 것입니다.

문제를 풀면서 계속 출력초과 에러가 발생해서 계속 고민을 하다가 아주 큰 음수 가중치를 계속 더하면 언더플로우가 발생할 수 있다는 것을 깨달았습니다.
그래서 upper 배열 값을 long 타입으로 바꿨더니 해결이 되었습니다.

---

⌨️ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class _11657_타임머신 {
   static class Edge {
      int to, weight;

      public Edge(int to, int weight) {
         this.to = to;
         this.weight = weight;
      }
   }
   final static int INF = 1000000000;
   static long[] upper;
   static int V, E;
   static ArrayList<Edge>[] adj;

   static boolean bellmanFord(int src) {
      upper = new long[V + 1];
      Arrays.fill(upper, INF);
      upper[src] = 0;
      for(int iter = 1; iter <= V; ++iter) {
         boolean chk = false;
         for(int here = 1; here <= V; ++here)
            for(int i = 0; i < adj[here].size(); ++i) {
               int there = adj[here].get(i).to;
               int cost = adj[here].get(i).weight;
               if(upper[here] != INF && upper[there] > upper[here] + cost) {
                  upper[there] = upper[here] + cost;
                  chk = true;
                  if(iter == V) return false;
               }
            }
         if(!chk) return true;
      }
      return true;
   }

   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      V = sc.nextInt();
      E = sc.nextInt();
      adj = new ArrayList[V + 1];
      for(int i = 0; i <= V; i++) adj[i] = new ArrayList<Edge>();
      for(int i = 0; i < E; i++) {
         int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
         adj[u].add(new Edge(v, w));
      }
      if(bellmanFord(1))
         for(int i = 2; i <= V; i++)
            System.out.println((upper[i] == INF ? -1 : upper[i]));
      else
         System.out.println(-1);
      sc.close();
   }
}

---

📋 회고

• 언더플로우는 한 번도 못봤는데 염두해야 겠음..
• 벨만-포드