BOJ 1507 궁금한 민호

사용한 알고리즘

플로이드 와샬

알고리즘 설명

이 문제는 기존에 플로이드 와샬과 다르게 이미 최적화 되어 있는 도로에서 필요 없는 도로를 추적하는 형태로 되어 있다.
플로이드 와샬의 최적화 조건인 “adj(i)(j) > adj(i)(k) + adj(k)(j)”를 모두 만족해야 한다는 점에서 불가능 조건을 판단하고, 필요없는 노드 판단은 “adj(i)(j) == adj(i)(k) + adj(k)(j)”와 같은 경우 (i->j) 연결을 (i->k, k->j)가 대신할 수 있으므로 i->j와 j->i 연결을 없애준다.
연결되어 있는 도로의 합을 출력한다.

풀이

// baekjoon 1507 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=21;

int N, adj[MAX_N][MAX_N], connect[MAX_N][MAX_N];

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++)
		for (int j=0; j<N; j++)
			scanf("%d", &adj[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 == j || i == k || k == j) continue;
				// (i->j)와 (i->k, k->j)
				if (adj[i][j] == (adj[i][k] + adj[k][j])) connect[i][j] = connect[j][i] = 1;
				if (adj[i][j] > adj[i][k] + adj[k][j]) return !printf("-1\n");
			}
		}
	}

	int ret = 0;
	for (int i=0; i<N; i++)
		for (int j=i+1; j<N; j++)
			if (!connect[i][j])
				ret += adj[i][j];

	printf("%d\n", ret);
	return 0;
}