[백준] 1507번: 궁금한 민호 - C++

문제

강호는 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을 출력한다.

---

어제 풀었던 플로이드 와샬 알고리즘 문제(11404번: 플로이드)를 역으로 생각하는 문제.

 

입력으로 주어진 값이 이미 플로이드-와샬 알고리즘을 적용한 상태라고 생각하고 접근하면 된다. 바로 갈 수 있는 경로가 있는 반면, 다른 도시를 거쳐서 갈 수 있는 경로 역시 존재하기 때문에 i에서 j(또는 j에서 i)까지 이동시간 city[i][j]이 i에서 k, k에서 j까지의 이동시간의 합과 같다면 이는 i ➡ k ➡ j로 거쳐서 가는 경로이므로 도로에 포함하지 않는다. 이를 noroute라는 bool 배열을 통해 관리해준다.

 

이 때, 예제 입력 4 처럼 i ➡ j로의 이동시간이 i ➡ k ➡ j보다 클 경우는 불가능하기 때문에 -1을 출력해준다.

 

코드

#include <cstdio>
#define MAX 21

int city[MAX][MAX];
bool noroute[MAX][MAX];

int main(void) {
    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            scanf("%d", &city[i][j]);
        }
    }
    
    for(int k = 0; k < N; k++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(city[i][j] > city[i][k] + city[k][j]) {
                    printf("-1\n");
                    return 0;
                }
                if(i != k && j != k && city[i][k] + city[k][j] == city[i][j]) 
                    noroute[i][j] = true;
            }
        }
    }

    int count = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(!noroute[i][j]) count += city[i][j];
        }
    }

    printf("%d\n", count / 2);
    return 0;
}