1507번

1507번 - 궁금한 민호

일단 처음에 주어진 입력값을 가지고 플로이드 알고리즘을 다시 수행했다.

그렇게 되면 모든 간선이 연결되어 있게 된다.

그 중에서 이제 삭제할 간선을 선택해야 한다.

삭제할 간선은 i - j 가 있고, i 에서 k를 거쳐서 j 로 가는 i - k - j 가 있다고 할 때,

현재 i 와 k 와 j 정점은 세개의 간선으로 삼각형으로 연결되어 있을 것이다. 그리고 우리는 i - j 의 최단 거리를 안다.

이를 통해 세가지 경우의 수를 알 수 있다.

1번째 경우

- D[i][j] > D[i][k] + D[k][j] 는 불가능한 경우이다. 우리는 D[i][j] 값이 최솟값인 걸 문제에서 줬기 때문이다. 그러므로 -1 출력

2번째 경우

- D[i][j]==D[i][k] + D[k][j] 는 i 에서 곧바로 j 로 가는 간선을 지워도 상관없음을 의미한다. 

3번째 경우

- D[i][j] < D[i][k] + D[k][j] 는 올바른 값이고, i 에서 곧바로 j 로 가는 간선은 지울 수 없다.

##내가 실수한 부분

1. 나는 처음에 3번째 경우에서 i-k 와 k-j 를 지워도 된다고 생각했었다. i-k 와 k-j 는 다른 경우에서 사용될 수 있으므로

지우면 안되는 간선이었다. 3번째 경우는 아무것도 하지 않고 놔두면 됐다. 만약 지워질 간선이라면 for문을 돌면서

지워질 것이기 때문이다. (코드에서 주석으로 처리된 부분이 실수했던 부분)

2. i 와 k가 같을때,  k 와 j가 같을 때, i 와 j 가 같을 때를 알고리즘 과정에서 빼야하는데 그러지 않았다.

원래 플로이드 워셜에서는 도달할 수 없을 때 INF 로 놓고 풀었지만, 여기서는 문제 특성상 0 값을 INF 로 놓으면 안됐다.

그래서 0을 그대로 가지고 풀어야 하는데, i==j 이거나 i==k 이거나 j==k 면  항상 두번째 케이스에 들어가게 되어

모든 간선이 지워지게 된다.

<정답 코드>

#include<iostream>
 
using namespace std;
int D[21][21];
const int INF = 987654321;
bool unuse[21][21];
int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> D[i][j];
        }
    }
 
 
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i!=k && j!=k && i!=j)
                {
                    if (D[i][j] == D[i][k] + D[k][j])
                    {
                        unuse[i][j] = true;
                        //unuse[i][k] = false;
                        //unuse[k][j] = false;
                    }
                    else if(D[i][j] > D[i][k] + D[k][j])
                    {
                        printf("-1\n");
                        return 0;
                    }
                    /*
                    else if(D[i][j] < D[i][k] + D[k][j])
                    {
                        //unuse[i][j] = false;
                        unuse[i][k] = true;
                        unuse[k][j] = true;
                    }
                    */
                }
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            if (unuse[i][j]==false)
            {
                ans += D[i][j];
            }
        }
    }
 
    cout << ans << endl;
 
    return 0;
}