[Algorithm]Baekjoon 1507번 :: 궁금한 민호

https://www.acmicpc.net/problem/1507

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n;
int arr1[20][20];
int arr2[20][20];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr1[i][j];
            arr2[i][j] = arr1[i][j];
        }
    }
 
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (k == i || k == j) continue;
 
                if (arr1[i][j] > arr1[i][k] + arr1[k][j])
                {
                    cout << -1;
                    return 0;
                }
                else if (arr1[i][j] == arr1[i][k] + arr1[k][j])
                {
                    arr2[i][j] = 0;
                }
            }
        }
    }
 
    int result = 0;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            result += arr2[i][j];
        }
    }
 
    cout << result / 2;
}
 
 

 

최단경로값들이 적혀있는 인접배열이 주어졌을 때, 최소한의 도로와 그 도로의 시간값들의 누적값을 구하는 문제이다.

 

알듯말듯 하다가 정답까진 안떠올라서 풀이를 봤는데 그렇게 어렵지는 않았다.

이런 유형자체도 꽤나 나올 것 같으니 잘 알아두는게 좋을 것 같다. (실제로 골드2치고 정답률이 높음)

 

일단 플로이드로 모든 경로를 체크해본다.

중간경로인 k가 i(시작지점)이거나 j(도착지점) 일 경우, 그냥 무시해준다.

arr[i][j] 값이 arr[i][k] + arr[k][j]보다 클 경우, 즉 입력으로 주어진 인접배열이 엉터리일경우 -1을 출력한다.

arr[i][j]값이 arr[i][k] + arr[k][j]값과 같을 경우, 즉 중복되게 입력된 경우 정답용 배열에 0을 입력해준다.

최소한의 도로만을 구해야하니 중복된값 한개는 없애줘야 한다.

 

이후 정답용배열의 모든값을 더한 후, 2로 나눠서 출력해주면 된다.

인접배열은 대각선대칭이니, 2로 나눠줘서  출력해야 최소거리값들만 출력된다.