백준 1956 운동 (C++)

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

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;

int dist[401][401];


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int v, e;
    int ans = INF;

    cin >> v >> e;

    fill_n(*dist, 401 * 401, INF);


    for (int i = 0; i < e; i++) {

        int start, end, di;

        cin >> start >> end >> di;

        dist[start][end] = di;

    }


    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= v; i++) {
        ans = min(ans, dist[i][i]);
    }

    if (ans == INF) {
        cout << -1;
    } else {
        cout << ans;
    }


    return 0;
}

1. 문제

방향성 그래프의 vertex, edge의 개수와 각 edge의 source, sink, dist가 주어진다. 이 그래프의 특정 지점에서 시작하여 다시 돌아오는 cycle이 있다면 해당 cycle의 최소 거리를 출력하라. cycle이 없다면 -1을 출력하라.

2. 풀이

사이클이라는 것은 어떤 노드 n이 있을 때 n->n 까지의 경로를 뜻한다. 이는 최대 버텍스의 수 만큼 있을 것이고, 이 거리 중 최솟값을 구하는 문제이므로 모든 경로를 탐색하는 floyd algorithm을 사용하여 풀 수 있다.

    int ans = INF;
    
    fill_n(*dist, 401 * 401, INF);
    
	for (int i = 0; i < e; i++) {

        int start, end, di;

        cin >> start >> end >> di;

        dist[start][end] = di;

    }

우선 dist 배열을 초기화하고, dist[시작점][끝점]=거리의 형태로 저장한다.

    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

플로이드 알고리즘을 이용하여 all pairs shortest path를 구해준다. 간단히 설명하자면 각 노드의 쌍에 대해 중간 노드를 잡고 edge relaxation을 수행하는 알고리즘이다.

    int ans = INF;


	for (int i = 1; i <= v; i++) {
        ans = min(ans, dist[i][i]);
    }

    if (ans == INF) {
        cout << -1;
    } else {
        cout << ans;
    }

위에서 언급했듯이 cycle은 k->k로 가는 최단 경로이다. 각 노드에 대해 i->i로 가는 최단 거리를 업데이트 해준다. 어떤 업데이트도 이루어지지 않았다면 cycle이 없음을 뜻하므로 -1을 출력하고, 최단 거리를 찾았다면 이를 출력해준다.