[JAVA] 백준 11657 벨만-포드

 

 

 

 

11657번: 타임머신

문제

도시들과 도시들 사이에 지나는 버스 그리고 버스가 목적지 도시로 이동하는데 걸리는 시간이 주어졌을 때 최단 거리를 구하여라

단, 버스들은 음의 시간을 지나는 시간이 있을 수 있다. 즉, 시간을 거슬러올라가는 타임머신 버스가 있다.

풀이

해당 문제는 음의 가중치가 존재하기 때문에 다익스트라로는 해결할 수 없고 벨만-포드 알고리즘을 통해 풀어야 합니다.

벨만-포드 알고리즘

벨만-포드 알고리즘은 전체 노드가 N일때 N-1번 모든 간선을 돌면서 최단거리를 구하는 알고리즘입니다.

벨만-포드 알고리즘에서는 음의 사이클을 발견할 수 있는데 N-1번 모든 간선을 반복한 후, 한번 더 모든 간선을 반복하고 변경된 distance가 있다면 음의 사이클이 있다는 것을 발견할 수 있습니다.

• 음의 사이클이란? : 음의 사이클은 A → B → C → A 라는 사이클이 존재할 때 만약 하나의 간선이라도 음의 가중치를 가지고 있다면 최단 거리가 무한히 작아지는 사이클입니다.

📌 입력

      long[] distance = new long[N];
      Bus[] buses = new Bus[M+1];

      Arrays.fill(distance, INF);

      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());

          buses[i] = new Bus(a, b, w);
      }
    static class Bus{
        int start;
        int destination;
        int weight;

        Bus(int start, int destination, int weight){
            this.start = start;
            this.destination = destination;
            this.weight = weight;
        }

    }

distance : 최단 거리를 저장해둘 배열을 선언합니다.

buses : 각 도시들을 지나다니는 버스배열을 선언합니다. (여기서 버스는 간선을 의미합니다.)

Bus : 각 간선들은 출발지, 목적지, 가중치(시간)을 가지도록 설정합니다.

📌 벨만-포드 알고리즘 구현

      distance[1] = 0;
      for(int i=1; i<N-1; i++){
          for(int j=0; j<M; j++){
              Bus bus = buses[j];
              if(distance[bus.start] != INF && distance[bus.destination] > distance[bus.start] + bus.weight){
                  distance[bus.destination] = distance[bus.start] + bus.weight;
              }
          }
      }

distance[1] = 0 : 여기서는 출발지 도시가 1번이라고 했기 때문에 첫 번째 도시로 가는 비용을 0으로 설정합니다.

벨만-포드 알고리즘 순서

1. 그래프 정점의 수 N-1번 반복을 진행합니다.
2. 한번의 반복에 모든 간선 즉, 여기서는 버스들을 모두 방문하면서 최단 거리를 갱신합니다.
3. 만약 현재 버스가 출발하는 도시의 distance가 무한대가 아니고, 현재 버스가 목적지로 하는 최단 거리가 (현재 버스의 출발지까지의 최단거리 + 현재 버스가 목적지까지 가는데 걸리는 시간)보다 크다면 distance 배열을 갱신합니다.
   • 쉽게 말해 A → B라는 최단 거리가 발견되어 있을 때 A → B보다 A → C → B가 더 빠른 시간내에 갈 수 있다면 갱신한다는 의미입니다.

📌 벨만-포드 알고리즘 음의 사이클 발견

        for(int j=0; j<M; j++){
            Bus bus = buses[j];
            if(distance[bus.start] != INF && distance[bus.destination] > distance[bus.start] + bus.weight){
                System.out.println(-1);
                return;
            }
        }

앞에서 한번의 반복에 모든 버스들을 돌면서 최단 거리를 갱신한다고 했는데, 만약 모든 정점의 수 N-1번 후 다시 모든 버스를 돌면서 최단 거리를 갱신하려고할 때, if문을 통과하는 경우가 있다면 이는 음의 사이클이 존재한다는 의미이므로 -1을 출력하고 종료했습니다.

📌 출력

        StringBuilder sb = new StringBuilder();
        for(int i=2; i<N; i++){
            sb.append(distance[i] != INF ? distance[i] : -1).append("\n");
        }

        System.out.println(sb);

출발지 도시를 제외하고 모든 도시까지의 최단 거리를 출력합니다.

만약 거리가 무한대라면 -1을 출력합니다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine() , " ");

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

      long[] distance = new long[N];
      Bus[] buses = new Bus[M+1];

      Arrays.fill(distance, INF);

      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());

          buses[i] = new Bus(a, b, w);
      }

      distance[1] = 0;
      for(int i=1; i<N-1; i++){
          for(int j=0; j<M; j++){
              Bus bus = buses[j];
              if(distance[bus.start] != INF && distance[bus.destination] > distance[bus.start] + bus.weight){
                  distance[bus.destination] = distance[bus.start] + bus.weight;
              }
          }
      }

        for(int j=0; j<M; j++){
            Bus bus = buses[j];
            if(distance[bus.start] != INF && distance[bus.destination] > distance[bus.start] + bus.weight){
                System.out.println(-1);
                return;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=2; i<N; i++){
            sb.append(distance[i] != INF ? distance[i] : -1).append("\n");
        }

        System.out.println(sb);

    }

    static class Bus{
        int start;
        int destination;
        int weight;

        Bus(int start, int destination, int weight){
            this.start = start;
            this.destination = destination;
            this.weight = weight;
        }

    }

}

결과