[1956] 운동

문제 링크 : https://www.acmicpc.net/problem/1956

1956 - 운동

본문

$V$개의 마을와 $E$개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 $1$번부터 $V$번까지 번호가 매겨져 있다고 하자.

당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.

도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

입력

첫째 줄에 $V$와 $E$가 빈칸을 사이에 두고 주어진다. ($2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)$) 다음 $E$개의 줄에는 각각 세 개의 정수 $a, b, c$가 주어진다. $a$번 마을에서 $b$번 마을로 가는 거리가 $c$인 도로가 있다는 의미이다. ($a \rightarrow b$임에 주의) 거리는 $10\,000$ 이하의 자연수이다. ($a, b$) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

제한

시간 제한	메모리 제한
2sec	192MB

---

풀이

모든 지점에 대하여 다시 그 지점으로 최단경로로 돌아올 수 있는가를 묻는 문제이다. ‘모든 지점에서 최단경로’를 찾는 문제이므로, 플로이드 워셜 알고리즘을 사용하여 문제를 해결해야한다.

플로이드 워셜 알고리즘은 직관적이며 구현이 간단하다는 장점이 있다. 따라서 조건만 맞춰놓고 알고리즘을 돌리면 정답을 직관적으로 확인할 수 있다는 것이다.

플로이드 워셜 알고리즘을 구현하기 위해서는 그래프를 2차원 행렬로 나타내야한다. 2차원 행렬에 대해 각 칸은 “시작점에서부터 도착지점까지의 최단경로의 가중치”를 의미한다. 만약 가중치가 INF라면 경로가 존재하지 않는다는 의미이다. 이 문제에서는 도시에 가만히 있는다는 선택지는 존재하지 않으므로, 같은 지점으로의 경로 또한 없다고 가정한다. (dist[i][i] = INF)

이후 플로이드 워셜 알고리즘을 통해 모든 지점에 대한 최단경로를 계산한다. 이후 우리는 1가지만 확인하면 된다.

시작점에서부터 다시 시작점으로 도달하는 경로가 있는가?

이를 확인하는 방법은 간단하다. 모든 정점에 대해 dist[i][i]가 INF인지 확인하면 된다. INF라면 경로가 존재하지 않는다, 즉 사이클이 불가능하다를 의미하고, 만약 어떤 특정한 값을 가지고 있다면 사이클이 존재한다고 말할 수 있다. 우리가 찾는 것은 사이클 중에서 가중치가 가장 적은 것을 찾는 것이므로, dist[i][i]의 값이 가장 작은 것을 찾으면 된다. 모든 정점에 대해 dist[i][i]가 INF라면, 그 어떤 마을도 선택할 수 없다고 받아들이면 된다.

• 참고 알고리즘 : 플로이드 워셜

코드

사용 언어 : C

최종 수정일 : 2024 / 4 / 29

#include <stdio.h>

#define MAX_IDX 400
#define INF 987654321

int grid[MAX_IDX + 1][MAX_IDX + 1];
int v, e;
int result = INF;

#define min(a, b) (((a) > (b)) ? (b) : (a))

void init() {
    for (int i = 1; i <= v; ++i) {
        for (int j = 1; j <= v; ++j) {
            grid[i][j] = INF;
        }
    }
    return;
}

int main() {
    scanf("%d %d", &v, &e);
    init();

    while (e--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        grid[a][b] = c;
    }

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

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

    if (result == INF) {
        printf("-1");
    } else {
        printf("%d", result);
    }
    return 0;
}

• grid[][] : 각 지점의 최단경로를 나타내는 2차원 행렬