백준 1507번 : 궁금한 민호 - 플로이드 활용 C++

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

1507번: 궁금한 민호

1.문제설명

INPUT

5
0 6 15 2 6
6 0 9 8 12
15 9 0 16 18
2 8 16 0 4
6 12 18 4 0

OUTPUT

55

문제에서 N개의 노드가 있을 때

노드에서 노드로 가는 모든 최단 거리를 INPUT으로 준다.

 

 

주어진 노드간 최단 거리를 유지하면서 간선의 개수를 최소로 할 때 

간선의 거리의 합을 구해야 한다.

 

 

---

2.접근방법[알고리즘]

 

주어진 인풋을 dist배열에 넣고

 

플로이드 워셜을 한번 실행했을 때

 

dist[i][k] + dist[k][j]) == dist[i][j]

이런 상황이 있으면 간선을 최소로 하기위해

dist[i][j] 의 간선을 사용하지 않고

dist[i][k] 와 dist[k][j]의 간선만 사용하면 된다.

 

 

맨 처음엔 문제에서 주어진 인풋의 간선을 모두 사용하는 걸 전제로 하고

위와 같은 간선이 있으면 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 || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

 

 

 

 

 

---

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;


const int INF = 0x3f3f3f3f;

int n, arr[21][21];

int dist[21][21];
bool ch[21][21];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dist, 0x3f, sizeof(dist));

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dist[i][j] = min(dist[i][j], arr[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 || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] < INF) sum += arr[i][j];
		}
	}

	cout << sum / 2 << '\n';



	return 0;
}