백준(BOJ) 1507번 궁금한 민호

문제 : 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이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값과 그 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

나의 풀이 :

플로이드 - 와샬 알고리즘을 통하여 모든 정점에서 모든 정점까지 최소 경로를 구하는데 거쳐서 가는 경우가 바로 가는 경우보다 큰 경우에는 따로 처리해주고 거쳐서 가는 경우와 바로 가는 경우가 같을 때에는  바로 가는 경우를 지워줌으로서 도로의 개수의 최솟값을 구하였다.

코드 ( C++ )

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int N;

const int MAX = 20;

int city[MAX][MAX];

bool citycopy[MAX][MAX];

int check;

void floyd()

{

// 거쳐가는 도시 k

for (int k = 0; k < N; ++k)

{

// 출발도시 i, 도착도시 j

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

{

if (i == k || j == k || i == j)

continue;

// 최소 경로가 성립하지 않는 경우 종료한다

if (city[i][j] > city[i][k] + city[k][j])

{

check = -1;

return;

}

// 바로 가는 경로를 없애준다.

else if (city[i][j] == city[i][k] + city[k][j])

{

citycopy[i][j] = false;

}

}

}

}

int main()

{

cin >> N;

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j) {

cin >> city[i][j];

citycopy[i][j] = true;

}

floyd();

if (check == -1) cout << -1 << endl;

else

{

int sum = 0;

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

{

if (citycopy[i][j])

{

sum += city[i][j];

}

}

// city[i][j]에 값과 city[j][i]에 값 둘다 구해주어서 합하였으므로 2로 나누어 준다.

cout << sum/2 << endl;

}

return 0;

}