[알고리즘] 백준 1507번: 궁금한 민호 (C++)

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

1507번: 궁금한 민호

이번 문제는 floydWarshall의 reverse였다.

>> 최단 경로가 갱신된 그래프를 반대로 초기의 상태로 만들어야 했다.

 

처음에는 아래 코드 (3) 번 조건에서 갱신이 되지 않은 그래프를 만드려고 graph[i][j]값에 INF를 할당했었는데

이는 최단 경로를 역 갱신하는 과정에서 오류를 발생시킨다.

INF값을 할당해버리면 그 다음 노드들을 검사했을 때, 2번 조건에 의해 종료가 되어버리는 오류가 생긴다.

>> 즉, 초기의 상태로 돌려두겠다고 그래프에 INF값을 할당하면 안 되는 문제였다.

>> 각 경로의 값을 그대로 두고, check배열을 선언하여 갱신되었던 경로라면 체크해두고, 결괏값을 구할 때,

그 경로는 무시한다.

 

이번 문제의 포인트는 '어떻게 갱신되었던 경로 값을 무시할 것인가'가 포인트였다.

>> 저 아이디어 자체로 보면 쉽지만 무시를 해야 하는가 갱신을 해야 하는가를 두었을 때, 어려웠던 문제다.

 

그리고, -1을 출력하는 조건은 이미 최단 경로들이 모두 갱신된 그래프가 주어졌기 때문에

최단 경로가 갱신되려 하면 -1을 출력해주면 되었다.

[AC 코드]

#include <iostream>
#define MAX_V 21
#define INF 987654321
using namespace std;

int n;
int graph[MAX_V][MAX_V];
bool check[MAX_V][MAX_V];

void floydWarshall(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                // (1)
                // ex) i = 1, k = 1, j = 2로 주어졌을 때
                // 이미 graph[i][k] = 0; 이라서 헛된 check가 갱신되기
                // 때문에 continue처리 시킨다.
                if (i == k || k == j) continue;
                
                // (2)
                // 이미 최단 경로로 모두 갱신되어있는 그래프다.
                // 새롭게 갱신이 된다는 것은 말이 안되기 때문에
                // -1을 출력한다.
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
				    cout << -1;
				    exit(0);
				}
				
		// (3)
		// 갱신했던 그래프를 찾아내어 해당 경로는 갱신이
		// 되었음을 check를 통해 알려준다.
		if (graph[i][k] + graph[k][j] == graph[i][j]) {
			check[i][j] = true;
		}
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> graph[i][j];
        }
    }
    
    floydWarshall();
    
    /*
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(graph[i][j] == INF) cout << "INF" << ' ';
            else cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
    */
    
    
    int result = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(check[i][j]) continue;
            result += graph[i][j];
        }
    }
    
    result /= 2; // ex) 1 -> 2, 2 -> 1을 모두 더했기 때문에 /= 2를 해준다.
    cout << result;
    
    return 0;
}