모든 정점에 대하여 ‘모든 정점으로'의 최단경로를 구하는 ‘플로이드 와샬' 알고리즘으로 풀었다.
i에서 j로 가는 것이 목표다.
i에서 j로 바로 가는 것이 가까운지 vs i에서 거쳐가는 정점 k로 가고, k에서 결국 j로 가는 것이 가까운지를 비교한다.
for(int k = 0; k < n; k++){ // 거쳐가는 정점
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int n;
int arr[102][102];
void floyd() {
for(int k = 0; k < n; k++){ // 거쳐가는 정점
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j< n; j++){
cin >> arr[i][j];
if(arr[i][j] == 0) arr[i][j] = INF;
}
}
floyd();
for(int i = 0; i < n; i++){
for(int j = 0; j< n; j++){
if(arr[i][j] == INF) cout << 0 << ' ';
else cout << 1 << ' ';
}
cout << '\n';
}
return 0;
}728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 이중 우선순위 큐 백준 7662번 c++ (0) | 2022.02.24 |
|---|---|
| Z 백준 1074번 c++ (0) | 2022.02.23 |
| 다리 놓기 백준 1010번 c++ (0) | 2022.02.23 |
| 셀프 넘버 백준 4673 c++ (0) | 2022.02.22 |
| 명령 프롬프트 백준 1032번 c++ (0) | 2022.02.22 |