백준 - 11657 타임머신 -Java + 벨만-포드

백준 타임머신 문제를 풀어보았다.

이번 문제에서는 음수 가중치가 포함되며, 음수 사이클이 존재하는지도 판단해야 하는 문제로 다익스트라 알고리즘을 적용하지 못하고 벨만-포드 알고리즘을 적용해 보는 가장 기초적인 문제이다.

문제를 풀고, 벨만-포드 알고리즘에 대해서도 정리한다.

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

11657번: 타임머신

---

문제 설명

 

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

• 한 도시에서 출발하여 다른 도시에 도착하는 버스가 있다 (방향 그래프)
• 만약 걸리는 시간 C가 0이면 순간이동, C가 음수이면 타임머신으로 시간을 되돌아간다
• 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 출력
• 무한히 오래전으로 되돌릴 수 있다는 것은 음수 사이클이 존재한다는 의미

제한 조건을 보면 도시의 수 보다 버스 노선의 수가 훨씬 많기 때문에 인접 리스트로 그래프를 구현한다

음수 사이클 존재여부와 음수 가중치가 있으므로 벨만-포드 알고리즘을 통해 최단 시간을 구한다

---

벨만 - 포드 알고리즘

• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행 가능
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간복잡도 O(VE)

https://devowen.com/250

벨만-포드 알고리즘을 적용해보자

 

1. 인접 리스트로 그래프를 구현한다. (노드 번호, 가중치)

• 1번 노드 - (2, -4), (3, 5), (4, 2), (5, 3)
• 2번 노드 - (4, -1)
• 3번 노드 - (4, -7)
• 4번 노드 - (5, 6)
• 5번 노드 - (4, -4)

2. 최단거리 배열 distance를 생성한다. (시작점의 가중치는 0으로 초기화)

1	2	3	4	5
0	INF	INF	INF	INF

3. 최단 경로를 업데이트한다.

 

반복 횟수는 N-1번, 모든 노드에 대해서 탐색하며, 노드 번호: s distance[s] != INF이어야 한다

• 노드가 N개이면 최단 경로라면 최대 N-1개의 에지로만 구성이 되어야 한다.
• 이해가 안 된다면 그림을 그려보면 된다 절대 N-1보다 많은 에지로 최단경로를 구성할 수 없다

반복 횟수 N-1의 의미

• 첫 번째 시작 노드에서 최단 경로를 업데이트하는 것은 1개의 에지로 갈 수 있는 최단 경로를 의미
• 두 번째 탐색에서는 에지 2개로 갈 수 있는 최단 경로 업데이트를 의미
  • 한 번 첫 번째 에지로 최단 경로가 업데이트된 상태에서 한 번 더 최단 경로 업데이트

---

최단 경로 배열 업데이트 과정

1	2	3	4	5
0	INF	INF	INF	INF

초기화

---

시작 노드 1번부터 distance[s]가 INF 아닌 모든 노드를 순회 -> 1번 노드만 INF가 아니므로 1번 노드만 진행

distance[target] > distance[s] + s.weight 이면 업데이트 진행

1	2	3	4	5
0	-4	5	2	3

---

모든 노드가 1번 시작점으로부터 에지 하나로 업데이트가 되었기 때문에 INF값이 아니므로 전체 노드에 대해서 최단 경로 업데이트

• 에지 2개로 갈 수 있는 최단 경로 업데이트라는 의미

1번 노드에 대해서부터 시작 -> 아무런 변화 X (값이 모두 동일)

2번 노드에 대해서 시작 -> distance[4] > distance[2] + 2->4 weight: 2 > -4 + -1 = -5이므로 업데이트 

1	2	3	4	5
0	-4	5	-5	3

모든 노드에 대해 반복

 

1	2	3	4	5
0	-4	5	-5	3

결과

---

다시 1번 노드부터 INF가 아닌 모든 노드들에 대해 최단 경로 업데이트

• 3개의 에지를 통해 갈 수 있는 최단경로를 업데이트한다는 의미

...

이를 N-1번 즉 4번까지 반복하면 되는데, 이미 3번 째부터 업데이트되는 곳이 없음

---

N-1번을 마쳤을 때의 의미

• 최대 4개의 에지를 사용해서 최단 경로를 업데이트했다. (N=5)

 

여기서 한 번 더 업데이트를 진행하면?

N번 업데이트를 마쳤을 때의 의미

• 업데이트된 값이 있다면
  • 음수 사이클이 존재
  • 5개의 노드가 존재했고, 4개의 에지로 업데이트를 해줬고, 한 번 더 업데이트를 했는데 업데이트된 값이 있다면 에지 5개로 최소 경로가 되는 경우 -> 음수 사이클
• 업데이트된 값이 없다면
  • 음수 사이클은 존재하지 않는다

반복의 의미와 distance != INF 인 모든 노드에 대한 탐색의 의미를 잘 이해하여야 응용할 수 있을 것이다.

---

풀이 코드

 

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

class Main{
    static class City{
        int num, w;
        public City(int num, int w){
            this.num=num; this.w=w;
        }
    }
    public static List<ArrayList<City>> graph = new ArrayList<>();
    public static int[] d, visited;
    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()), m = Integer.parseInt(st.nextToken());
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            graph.get(s).add(new City(e, w));
        }
        long[] distance = new long[n + 1];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[1] = 0;
        // 정점의 개수 -1번 동안 최단거리 업데이트 + 한 번 더 업데이트체크(음수 사이클 )
        for(int i=1; i<=n; i++){    // i개의 에지(간선)를 이용했을 때의 최단거리 업데이트
            for(int j=1; j<=n; j++){    // 1번 노드부터 n번 노드까지
                if(distance[j] == Long.MAX_VALUE) continue;
                for(City city : graph.get(j)){
                    if(distance[city.num] > distance[j] + city.w){
                        if(i == n){
                            System.out.println("-1");
                            br.close();
                            return;
                        }
                        distance[city.num] = distance[j] + city.w;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=n; i++){
            if(distance[i] == Long.MAX_VALUE) sb.append("-1\n");
            else sb.append(distance[i]+"\n");
        }
        System.out.print(sb);
        br.close();
    }

}

• 가중치 저장을 위한 City 클래스 객체 이용
• 인접 리스트로 그래프 구현
• 첫 번째 반복문 = 에지의 개수 최대 N-1개이어야 하지만, 한 번 더 반복하여 음수 사이클 확인
• 두 번째 반복문 = 각 노드를 시작으로 탐색

사실 시작 노드가 1번이면 1번과 연결된 노드에 대해서 다음 반복문에 탐색이 시작되어야 하는데 첫 번째 반복문에 탐색하고, 그다음 반복문에서 중복으로 탐색한다. 논리적으로 옳지 않다고 생각하여 tmp 배열을 카피해서 위의 알고리즘과 동일하게 작동하도록 해봤는데, 반복문을 도는 것보다 Arrays.copyOf 메서드의 비용이 더 크게 나와 중복해서 반복하도록 두었다.

 

논리적으로 맞게 변경한 코드

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

class Main{
    static class City{
        int num, w;
        public City(int num, int w){
            this.num=num; this.w=w;
        }
    }
    public static List<ArrayList<City>> graph = new ArrayList<>();
    public static int[] d, visited;
    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()), m = Integer.parseInt(st.nextToken());
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            graph.get(s).add(new City(e, w));
        }
        long[] distance = new long[n + 1];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[1] = 0;
        // 정점의 개수 -1번 동안 최단거리 업데이트 + 한 번 더 업데이트체크(음수 사이클 )
        for(int i=1; i<=n; i++){    // i개의 에지(간선)를 이용했을 때의 최단거리 업데이트
            long[] tmp = Arrays.copyOf(distance, distance.length);
            for(int j=1; j<=n; j++){    // 1번 노드부터 n번 노드까지
                if(tmp[j] == Long.MAX_VALUE) continue;
                for(City city : graph.get(j)){
                    if(distance[city.num] > distance[j] + city.w){
                        if(i == n){
                            System.out.println("-1");
                            br.close();
                            return;
                        }
                        distance[city.num] = distance[j] + city.w;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=n; i++){
            if(distance[i] == Long.MAX_VALUE) sb.append("-1\n");
            else sb.append(distance[i]+"\n");
        }
        System.out.print(sb);
        br.close();
    }

}

---

다익스트라랑은 구현하는 게 완전히 다르고 반복하며 업데이트할 때의 의미도 약간 달랐다.

이유는 음수 가중치 때문이고 왜 그래야 하는지 이해할 수 있도록 정리했다

이유를 정확히 알아야 코테문제에 나와도 구현할 수 있을 것 같다