[백준 1507] 궁금한 민호

 

 그래프 이론 문제다. 처음 문제를 가볍게 읽었을 때는 최소 스패닝 트리 문제인 줄 알았다. 하지만 문제를 꼼꼼하게 읽다 보니 개성 있는 문제라고 느꼈는데, 각 노드에서 목적 노드 별 최단 거리가 주어지고 최소 간선으로 그 그래프를 만들었을 때 간선의 비용 총합을 추측하는 문제였다.

 

 먼저 시도했던 방법은, 최소 스패닝 트리를 만들듯이 간선들을 우선순위 큐에 넣고 비용이 작은 간선을 우선해서 그래프를 만들어 나가는 방법이었다. 이 방법으로 구현하다가 결국에는 다른 노드를 경유해서 만들어질 수 있는 최단 거리 문제 때문에 중간에 지워버렸다. 매 간선을 추가하려고 할 때마다 DFS가 필요할 테니까.

 

 그다음으로 이용한 방법은, 플로이드-워셜 알고리즘을 이용한 방법이었다. 문제에서 주어지는 입력값은 결국 어떤 그래프에 대해 플로이드-워셜 알고리즘을 돌린 결과다. 그리고 문제에서는 간선의 개수가 최소인 형태의 그래프를 기준으로 하게 되어있다. 따라서 되도록이면 노드와 노드 간 직접 연결된 간선이 최소 값에 해당하지 않도록 하는 그래프를 찾아내야 하는 것이다.

 

 나는 모든 노드가 직접 연결되어 있는 완전 그래프의 형태에서 시작해, 굳이 직접 연결될 필요가 없는 간선을 찾아내기로 했다. 모든 노드가 연결된 완전 그래프라고 가정하면서 대해 플로이드-워셜 알고리즘을 다시 돌려보는 것이다. 그럼 루프 속에서 세 가지의 경우를 볼 수 있다.

 

dist[i][j] > dist[i][k] + dist[k][j]인 경우: 특정 노드를 경유해서 가는 비용 합이 입력 값으로 받은 비용보다 작은 경우. 이것은 모순이다. 이미 입력 값은 각각의 최단 경로를 보장하고 있으며, 다른 노드를 경유한 비용 합이 이보다 더 작다면 애초에 잘못된 입력 값이라는 소리다. 따라서 발견하는 순간 -1을 출력하고 종료한다.

dist[i][j] == dist[i][k] + dist[k][j]인 경우: 특정 노드를 경유해서 가는 비용 합이 입력 값과 같은 경우. 완전 그래프를 상상할 때, 두 값이 같다면 굳이 직접 이어지는 간선을 유지할 필요가 있을까? 문제에서 최소 간선 수를 요구하고 있기 때문에 당연히 직접 이어지는 간선이 필요 없는 경우가 된다. 따라서 노드 i와 j 사이의 간선을 불필요하다고 저장해 둔다. 나는 2차원 배열에 이 정보를 저장했다.

dist[i][j] < dist[i][k] + dist[k][j]인 경우: 특정 노드를 경유해서 가는 비용 합이 입력 값보다 큰 경우. 이 경우에는 당연히 노드 i와 j 사이의 간선이 여전히 필요한 상태다. 물론 경유하는 k가 바뀌면, 후에 필요 없다고 판별하게 될 수도 있으나 당장 이 상황에서는 간선을 유지해야 한다. 따라서 간선에 대한 정보를 따로 업데이트하지 않는다.

 

 위와 같이 판별하며 플로이드-워셜 알고리즘을 모두 끝내고 나면, 제거할 수 있는 불필요 간선들에 대한 정보를 얻게 된다. 물론 잘못된 입력 값이었다면 이미 -1을 출력하고 프로그램이 종료되었을 것이다. 이후엔 필요한 간선들에 대해서만 그 비용들을 확인해 모두 더해서 출력하면 되는데, 여기서 주의할 것은 무방향 그래프를 기준으로 하고 있으므로 비용의 총합을 2로 나누어서 출력해 준다. 쉽게 말하면 i->j에 대한 비용 정보와 j->i에 대한 비용 정보가 모두 더해진 상황이라 이를 처리해 주는 것이라고 생각하면 된다.

 

 주어지는 N의 범위가 최대 20으로 상당히 작기 때문에, 좀 더 오래 걸리는 알고리즘이 바로 떠오른다면 그것을 사용해도 무방할 것 같다. 신선했던 문제.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, v;
    cin >> n;

    vector<vector<int> > dist(n, vector<int>(n));
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> dist[i][j];
        }
    }


    vector<vector<bool> > need(n, vector<bool>(n, true));
    bool isValid = true;

    for(int k=0; k<n; k++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {    
                if(i!=j && i!=k && j!=k) {
                    if(dist[i][k]+dist[k][j]==dist[i][j]) {
                        need[i][j] = false;
                    } else if(dist[i][k]+dist[k][j]<dist[i][j]) {
                        cout << "-1";
                        return 0;
                    }
                }
            }
        }
    }

    int sum = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(need[i][j]) {
                sum+=dist[i][j];
            }
        }
    }

    cout << sum/2;
}