[백준] 1956번 - 운동 (Gold 4)

문제 링크

백준 1956번 - 운동 (Gold 4)

문제 설명

V개의 점과 E개의 간선으로 이루어진 그래프가 주어져 있을 때 가장 작은 길이의 사이클을 구하시오.
사이클의 길이란 사이클을 이루고 있는 간선의 가중치의 합이며, 간선의 가중치는 항상 양수이다.
만일 사이클이 존재하지 않는다면, -1을 출력하시오.

정답 코드 및 설명

사이클은 출발지와 도착지가 같은 경로라고 생각할 수 있다.
따라서, 가능한 모든 출발지와 도착지에 대해 최단 경로를 찾아주는 플로이드-워셜 알고리즘을 사용하면 된다.
출발지와 도착지가 같은 n개의 최단 경로의 길이 중 최솟값이 사이클의 최소 길이가 되기 때문이다.

플로이드-워셜 알고리즘은 DP를 이용한 알고리즘이다.
이 알고리즘의 시간 복잡도는 $O(N^3)$으로, 단순하게 다익스트라를 N번 적용하는 $O(NE \log N)$보다 빠르다.
일반적으로 $E = O(N^2)$이기 때문이다.

구체적인 알고리즘은 아래와 같다.
점 i에서 점 j까지 이동하는, 경유점들이 집합 $\lbrace 1, 2, … ,k \rbrace$의 부분집합인 경로 중 최단 경로의 길이를 $dist_k (i, j)$라고 두자. 경유점이 집합 $\lbrace 1, 2, … ,k + 1 \rbrace$의 부분집합이 되는 경로 중 최단 경로의 후보로는 두 가지가 있다.

1. 경유점들이 집합 $\lbrace 1, 2, … ,k \rbrace$의 부분집합인 경로
   • 최단 경로의 길이는 $dist_{k} (i, j)$
2. 점 k+1을 경유하는 경로
   • 최단 경로의 길이는 $dist_{k} (i, k + 1) + dist_{k} (k + 1, j)$

따라서 $dist_{k+1} (i, j) = \textrm{min}(dist_{k} (i, j), dist_{k} (i, k + 1) + dist_{k} (k + 1, j))$가 성립한다. 처음 $dist_{0}(i, j)$는 중간 경유점이 없는 경로이므로, 주어진 간선들에 대응한다고 볼 수 있다. 이 때 불가능한 경로에 해당하는 값은 무한대로 초기화를 해줘야 한다.

이 문제에서는 시작점과 도착점이 같은 경우도 처음에 무한대로 초기화를 해주어야하는데, 이는 사이클을 구하는 문제이기 때문이다. 보통의 플로이드-워셜에서는 시작점과 도착점이 같은 경우는 최단 경로의 길이가 0인 경우로 취급하지만 이 문제에서는 그러면 사이클을 구할 수가 없다.

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

public class BOJ1956 {
    static final int MAX = 100000000;
    int v, e;
    int[][] roads;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        roads = new int[v][v];
        int start, end, dist;
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken()) - 1;
            end = Integer.parseInt(st.nextToken()) - 1;
            dist = Integer.parseInt(st.nextToken());
            roads[start][end] = dist;
        }
    }

    int[] FloydWarshall() {
        int[][] dist = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                if (roads[i][j] != 0) dist[i][j] = roads[i][j];
                else dist[i][j] = MAX;
            }
        }
        for (int k = 0; k < v; k++) {
            for (int i = 0; i < v; i++) {
                for (int j = 0; j < v; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        int[] cycle = new int[v];
        for (int i = 0; i < v; i++)
            cycle[i] = dist[i][i];
        return cycle;
    }

    int getMin(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (min > arr[i]) min = arr[i];
        }
        if (min == MAX) return -1;
        return min;
    }

    void solution() throws IOException {
        input();
        System.out.println(getMin(FloydWarshall()));
    }

    public static void main(String[] args) throws IOException {
        new BOJ1956().solution();
    }
}