[BOJ] #1956 운동

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

---

플로이드-워셜 알고리즘을 활용해서 그래프 내에서 가장 최소비용의 사이클 여부를 판별하는 문제이다. 사이클이 존재하면 가장 최소비용의 거리를, 존재하지 않으면 -1을 출력하면 된다.

여기서 "사이클" 이란, 자기 자신의 정점에서 출발에 다시 자기 자신으로 돌아오는 경로를 말한다. 따라서 필자는 플로이드-워셜 알고리즘을 이용해 출발정점과 도착정점이 같은 것들 중, 거리가 INF가 아닌 것들을 골라서 set 자료구조에 담고, set이 비어있으면 (즉, 자기 자신에서 자기 자신으로 돌아오는. 사이클이 존재하지 않으면) -1을 출력하고, 그렇지 않을 경우 set의 가장 첫번째 인자를 역참조하여 출력해내는 방식으로 설계하였다.

set을 쓴 이유는, BST 자료구조로 이루어져 있어 입력시에 O(log N)의 시간복잡도로 자동으로 오름차순 정렬을 할 수 있고, 어차피 가장 최소비용 사이클 하나만 출력하면 되기 때문에 중복 여부를 신경쓸 필요가 없었기 때문이다. 사실, vector에 담고 sort 시켜도 될테지만... algorithm 헤더와 sort 한줄 적는 것이 귀찮았기 때문이다 ㅋㅋㅋㅋ 아마 시간적으로는 set에 하나하나의 입력마다 정렬을 시켜주는 것 보다는 vector에 담고 sort로 한번에 정렬시키는 편이 더 빠를 것 같기는 하다. (실제로 확인해보니 vector를 사용한 코드가 약 0.01초 가량 더 빨랐다. 아래 제출 사진 참고)

단순히 플로이드-워셜을 사용하여 문제를 해결하는 것이 아닌 그래프 내에서의 사이클을 판별하고, 사이클의 가장 최소비용을 출력하는 문제였기 때문에 골드 하위문제임에도 불구하고 생각해내는데 시간이 좀 걸렸다.

---

#include <iostream>
#include <set>

#define MAX 401
#define INF 99999999

using namespace std;

int V,E;
int arr[MAX][MAX];

void floydWarshall() {
    for (int k=0; k<V; k++) {
        for (int i=0; i<V; i++) {
            for (int j=0; j<V; j++) {
                if (arr[i][k] != INF && arr[k][j] != INF)
                    arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
}

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

    cin >> V >> E;

    for (int i=0; i<V; i++) {
        for (int j=0; j<V; j++) {
            arr[i][j] = INF;
        }
    }

    for (int i=0; i<E; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        arr[a][b] = c;
    }

    floydWarshall();

    set<int> total;
    for (int i=0; i<V; i++) {
        for (int j=0; j<V; j++) {
            if (i==j && arr[i][j] != INF) {
                total.insert(arr[i][j]);
            }
        }
    }

    if (total.empty()) cout << -1 << '\n';
    else cout << *total.begin() << '\n';

    return 0;
}

첫번째 시도가 set / 두번째 시도가 vector에 담고 sort로 한번에 정렬시킨 코드이다. vector를 쓰는것이 0.01초 가량 더 빠르다...!