백준 1507 : 궁굼한 민호

문제 설명

---

모든 도시 쌍 사이의 최소 이동 시간을 구한 표가 주어진다. 민호는 이 표를 기반으로 최소한의 도로 개수로 모든 도시를 연결하려고 한다. 이때 필요한 도로의 최소 개수와 총 시간을 구하는 프로그램을 작성해야 한다.

---

 

나는 이 문제를 그리디 + 플로이드를 이용하여 풀었다. 코드의 핵심은 플로이드-워셜 알고리즘과 그리디 방식의 도로 선택이다. 즉, 주어진 표를 {(출발점), (도착점), (가중치)}꼴로 바꾸어 모든 노드를 저장하고, 이를 가중치를 기준으로 오름차순 정렬을 한 뒤, 가장 작은 가중치를 갖는 노드부터 탐색해가며 그래프를 만들어주는 방식이다. 노드를 추가할 때마다 플로이드를 이용하여 현재까지 추가된 노드만을 이용한 그래프의 모든 도시쌍사이의 최소이동시간 표를 만들어준다. 모든노드를 돌고, 완성된 표가 초기의 표와 같은지를 비교해 가능/불가능의 여부를 판단해준다. N범위가 20으로 작기에 O(N^5)으로 풀렸다.

---

소스 코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int arr[25][25];
int ans;
int res[25][25];

struct dat {
    int x, y, val;
};

bool comp(dat x, dat y) {
    return x.val < y.val;
}

vector <dat> vec;

int main()
{
    int i, j, k;
    scanf("%d", &n);
    for(i=0;i<=n;i++) {
        for(j=0;j<=n;j++) {
            arr[i][j] = 1e9;
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            scanf("%d", &res[i][j]);
            if(i < j) vec.push_back({i, j, res[i][j]});
        }
    }
    sort(vec.begin(), vec.end(), comp);
    for(int t=0;t<vec.size();t++) {
        int x = vec[t].x, y = vec[t].y, val = vec[t].val;
        if(arr[x][y] > val) {
            arr[x][y] = val;
            arr[y][x] = val;
            ans += val;
        }
        for(k=1;k<=n;k++) {
            for(i=1;i<=n;i++) {
                for(j=1;j<=n;j++) {
                    if(i == j) continue;
                    if(arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=n;j++) {
            if(i == j) continue;
            if(res[i][j] != arr[i][j]) {
                printf("-1");
                return 0;
            }
        }
    }
    printf("%d", ans);
    return 0;
}