[백준1507] 궁금한 민호 (C++)

📌 문제

BOJ 바로가기

도시 간의 최단거리 배열이 주어진다. 이 배열을 보고 도로의 최소 개수를 알아내야 한다.

🗡 풀이

📍 플로이드-워셜 알고리즘을 조금 변형해서 풀 수 있다. 도시 A에서 도시 B로 갈 때, 도시 C를 경유해서 갈 수 있는 경우 A에서 C로 가는 도시는 필요 없다. 따라서 도시를 삭제해준다.

else if (map[i][j] == map[i][k] + map[k][j])
	ans_map[i][j] = 0;

📍 문제에서 말하는 '불가능한 경우'는 입력으로 주어진 그래프가 최단거리 배열이 아닐 때이다.

else if (map[i][j] > map[i][k] + map[k][j]) {
	cout << "-1";
	return 0;
}

📍 처음에는 map배열에 직접 수정을 가해 주었는데, 이렇게 하면 반복문이 돌아가는 과정에서 오류가 발생할 수 있다. 못 가는 도로라는 의미로 0을 표시했는데 그 도로에 접근하게 되면 잘못된 답이 나온다.
따라서 ans_map배열을 만드는 대신 map배열에 직접 수정을 가하는 방식으로 푼다면 다음과 같이 map[i][k] != 0 && map[k][j] != 0 조건을 달아주어야 한다.

else if (map[i][k] != 0 && map[k][j] != 0 && map[i][j] == map[i][k] + map[k][j])
	map[i][j] = 0;
else if (map[i][k] != 0 && map[k][j] != 0 && map[i][k] + map[k][j] < map[i][j]) {
	cout << "-1";
	return 0;
}

🥶 연구소 문제도 그렇고 이 문제도 그렇고 역시 원본 저장을 꼬박꼬박 잘 해줘야 고생을 덜할듯 싶다..

🚩 소스코드

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, map[20][20], ans_map[20][20], sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			ans_map[i][j] = map[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 || j == k) continue;
				// 어딘가를 경유해서 갈 수 있는 도시인 경우 도로를 0으로 만들어준다. (못 가는 도로라는 의미)
				else if (map[i][j] == map[i][k] + map[k][j])
					ans_map[i][j] = 0;
				// 최단거리가 따로 존재하는 경우 예외처리 (잘못된 지도)
				else if (map[i][j] > map[i][k] + map[k][j]) {
					cout << "-1";
					return 0;
				}
			}
		}
	}
	// 정답 출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum += ans_map[i][j];
		}
	}
	cout << sum / 2;
	return 0;
}