[C++][백준] 궁금한 민호(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개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.
출력
첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.
풀이
플로이드와샬 알고리즘은 모든 정점에서 모든 정점까지의 최소 비용을 계산할 수 있습니다.
그러나 해당 문제의 경우 이미 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았습니다.
그러나 각 도시들의 구체적인 연결 정보에 대해서는 알 수 없습니다.
이 때 최소한의 연결 갯수를 구해야 합니다.
예를 들어 아래와 같이 모든 쌍의 도시에 대한 최소 이동 시간이 주어진다고 가정해봅시다.
이때 위와 같은 연결 정보를 가지고도 동일한 최소 이동 시간을 구할 수 있지만
이때 위와 같은 연결 정보를 가지고도 동일한 최소 이동 시간을 구할 수 있습니다.
왜 그럴까요?
1번 도시 → 2번 도시로 바로 가는 비용은 5,
1번 도시 → 3번 도시 → 2번 도시로 우회할 때 비용은 3이기 때문에
1번 도시에서 2번 도시까지의 최소 비용은 3입니다.
이때 아래와 같이 1번 도시 → 2번도시로 바로 가는 연결은 삭제해도 좋습니다.(최소 비용이 유지됩니다.)
그러나 1번 도시 → 2번도시로 바로 가는 연결이 아닌 1번 도시 → 3번 도시 연결을 삭제하는 경우 최소 비용이 3이 아닌 5가 될 것입니다.(기존 최소 비용 유지 안됨)
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
int value = map[i][j];
map[i][j] = INF;
map[j][i] = INF;
floyd();
if (map[i][j] != value) {
map[i][j] = value;
map[j][i] = value;
answer += map[i][j];
}
}
}여기서 아이디어를 얻어 모든 도시에서 모든 도시까지 연결되어 있는 상태에서
모든 연결에 대해 해당 연결이 끊겼을 때 기존 최소 비용을 유지할 수 있느냐를 통해
남겨둘 연결 / 제거할 연결을 판별하였습니다.
제거할 연결을 모두 삭제하면 문제에서 요구하는 최소한의 연결 갯수를 구할 수 있습니다.
※ 이 때 문제에 불가능한 경우에는 -1을 출력한다는 조건이 있는데, 저는 입력값이 모순된 경우라고 생각하였습니다.
이 경우 모든 쌍의 도시에 대해서 최소 이동 시간을 다시 한 번 계산하여 입력값과 비교하였습니다.
전체 코드는 아래와 같습니다.
#include <iostream>
using namespace std;
int N;
const int MAX = 25;
const int INF = 987654321;
int map[25][25];
int map2[25][25];
int min(int a, int b) {
if (a < b) return a;
else return b;
}
void floyd() {
for (int k = 1; k <= N; k++) { // 거쳐가는 수
for (int i = 1; i <= N; i++) { // 시작 정점
for (int j = 1; j <= N; j++) { // 종료 정점
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
bool floydTest() {
for (int k = 1; k <= N; k++) { // 거쳐가는 수
for (int i = 1; i <= N; i++) { // 시작 정점
for (int j = 1; j <= N; j++) { // 종료 정점
map2[i][j] = min(map2[i][j], map2[i][k] + map2[k][j]);
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] != map2[i][j]) {
return false;
}
}
}
return true;
}
int solution() {
int answer = 0;
if (floydTest() == false) {
return -1;
}
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
int value = map[i][j];
map[i][j] = INF;
map[j][i] = INF;
floyd();
if (map[i][j] != value) {
map[i][j] = value;
map[j][i] = value;
answer += map[i][j];
}
}
}
return answer;
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
map2[i][j] = map[i][j];
}
}
cout << solution();
return 0;
}