문제 링크 https://www.acmicpc.net/problem/1507
문제
강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.
도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.
강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.
예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.
모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고, 그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.
출력
첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.
풀이 과정
예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다.
그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면
최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다.
i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면
모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int N, M, result;
int num[21][21];
int res[21][21];
void floyd() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
// 거쳐가는 도시가 출발도시거나 도착도시일 경우
if (k == i || k == j) continue;
// 최소 경로가 성립하지 않는 경우 종료
if (num[i][j] > num[i][k] + num[k][j]) {
result = -1;
return;
}
// 바로 가는 경로 없애줌
else if (num[i][j] == num[i][k] + num[k][j]) {
res[i][j] = 0;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> num[i][j];
res[i][j] = num[i][j];
}
}
floyd();
if (result != -1) {
int sum = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
sum += res[i][j];
}
}
// i -> j 시간과 j -> i 시간이 중복 계산되어 있으므로 2로 나눠준다.
cout << sum / 2;
}
else cout << result;
}
댓글남기기