BOJ 1956 운동 (FloydWarshall 이용 최단 사이클 구하기)

문제

방향 그래프에서 가장 짧은 길이의 ‘사이클(Cycle)’ 구하기. (사이클이 없으면 -1 출력)

복잡도 분석

• 시간 복잡도: $O(V^3)$. 정점의 개수 $V \le 400$. $400^3 = 64,000,000$ (6천4백만) 연산으로 제한 시간 2초 내에 충분히 통과 가능
• 공간 복잡도: $O(V^2)$. 400 x 400 크기의 2차원 배열이므로 메모리 제한(256MB)에 전혀 문제없음.

접근법

• 플로이드-워셜의 응용: 일반적인 최단 경로 문제와 달리 “나에게서 출발해 다시 나에게로 돌아오는 거리” 를 구해야 한다.
• 대각선 INF 초기화: 일반적인 플로이드-워셜은 자기 자신으로 가는 거리를 dist[i][i] = 0으로 초기화한다. 하지만 이 문제에서는 dist[i][i] = INF로 초기화해야 한다. 그래야만 점화식 min(dist[i][i], dist[i][k] + dist[k][i])를 통해 $i \rightarrow k \rightarrow i$로 돌아오는 최단 사이클이 자연스럽게 갱신된다.
• 알고리즘 종료 후, $1$부터 $V$까지의 dist[i][i] 값 중 최솟값이 전체 그래프의 최단 사이클 길이이다. 갱신된 값이 없다면 사이클이 없는 것이므로 -1을 출력한다.

풀이

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g; 
int v,e;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>v>>e;
    g.assign(v+1,vector<int>(v+1,1e9)); // 0번 버림
    for(int i=0;i<e;i++){
        int a,b,c;cin>>a>>b>>c;
        g[a][b] = c;
    }

    // 원래 대각선은 0으로 초기화 시켰으나, 지금은 전부 inf로
    for(int k=0;k<v+1;k++){
        for(int a=0;a<v+1;a++){
            for(int b=0;b<v+1;b++){
                g[a][b] = min(g[a][b], g[a][k]+g[k][b]);
            }
        }
    }
    
    int min_res = 1e9;
    for(int i=0;i<v+1;i++){
        min_res = min(min_res,g[i][i]);
    }
    if (min_res!=1e9) cout << min_res;
    else cout << "-1";

    return 0;
}

\[dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])\]

플로이드 워셜은 코드가 쉬워서 k a b로 외워두고 몇 문제 생각없이 풀었었는데, 이렇게 사이클을 구할수 있다는걸 몰라서 그랬던건지 이 문제는 읽었을때 이해하는데 시간이 조금 걸렸다.

위의 식에서 목적지 j 자리에 i를 넣으면

\[dist[i][i] = \min(dist[i][i], dist[i][k] + dist[k][i])\]

초기에 대각선에 0을 둘 경우, 0보다 작을 수 없으므로 갱신이 일어나지 않게 된다. 그러나 여기서는 inf로 초기화를 했고

계산을 하다보면 1-2 최단경로, 2-1 최단경로가 더해지면서 1번 정점을 포함하는 사이클의 길이를 구할 수 있게 된다.

최단경로 구하기 + 음의 사이클 판독, 비정상 경로 판독

그리고 여기 코드에서 사용하지는 않았지만, 결과에서 대각선이 음수가 나올경우 음수 사이클이 있다는것을 확인 가능하다.

이 경우 음수 사이클과 접촉한 배열의 다른 경로값은 다 망가진 값이 된다.

음의 사이클이 있을때, 대각선 값이 항상 -inf가 되는건 아니다. 정해진 횟수만큼만 돌기 때문에… 그냥 음의 정수가 된다. 1회차 돌았을때 대각선이 0보다 작다면 그냥 수학적으로 -inf구나 라고 사람 머리로 판정하면 됨.

그런데 대각선이 음수인것을 보고, 강제로 -inf을 덮어씌워서 음수 사이클이라고 표기를 하고, 이것을 다시 플로이드 워셜을 돌리면 인접한 경로로 -inf가 전파된다.

2회차로 알고리즘을 돌렸을때 값이 -inf라면 음수 사이클을 거쳐간 오염 경로인것이고, 양수라면 정상 경로(진짜 최단거리), inf라면 도달 불가