백준 11404 _ 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

---

✨ 내 소스 코드

#include<iostream>
#include<algorithm>
using namespace std;

int bus[101][101] = { 0, };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (!bus[a][b]) {
			bus[a][b] = c;
		}
        //이미 노선이 있으면, 비용이 더 작은 것으로 값을 바꾸어준다
		else {
			bus[a][b] = min(bus[a][b], c);
		}
		
	}

	//플로이드 - 와샬
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (j == k) {
					bus[j][k] = 0;
					continue;
				}
				if (bus[j][i] && bus[i][k]){
					if (bus[j][k] == 0 && bus[j][i] + bus[i][k] == 0) {
						bus[j][k] = 0;
					}
					else if (bus[j][k] == 0) {
						bus[j][k] = bus[j][i] + bus[i][k];
					}
					else if (bus[j][i] + bus[i][k] == 0) {
						bus[j][k] = bus[j][k];
					}
					else {
						bus[j][k] = min(bus[j][k], bus[j][i] + bus[i][k]);
					}
				}
					
			}
		}
	}

	for (int i = 1;i <= n; i++) {
		for (int j = 1; j <= n;j++) {
			cout << bus[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

🙏 문제 풀이

🌱 플로이드 와샬

'플로이드-와샬' 이라는 것을 사용하여 문제를 해결하였다

플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 경로를 구하는데 좋은 알고리즘이라고 한다

토대는 기본적인 플로이드 와샬의 방식을 사용하였고

'algorithm'라이브러리의 min 함수를 이용하여 값을 구하다보니, 0은 값을 구하지 못할 때의 결과로 나와야 되는 것인데 이를 최소인 값으로 판별해버려서 다음과 같이 몇가지 예외 코드를 넣어주었다

 

if (j == k) {
	bus[j][k] = 0;
	continue;
}
if (bus[j][i] && bus[i][k]){
	if (bus[j][k] == 0 && bus[j][i] + bus[i][k] == 0) {
		bus[j][k] = 0;
	}
	else if (bus[j][k] == 0) {
		bus[j][k] = bus[j][i] + bus[i][k];
	}
	else if (bus[j][i] + bus[i][k] == 0) {
		bus[j][k] = bus[j][k];
	}
	else {
		bus[j][k] = min(bus[j][k], bus[j][i] + bus[i][k]);
	}
}

 

플로이드 와샬 문제는 아직 몇가지 풀어본 것이 없어서 완벽하게 이해를 하지 못한 것 같다

❗공부가 더 필요할듯❗

 

 

🌱 문제 풀이 결과