문제 보러가기 : https://www.acmicpc.net/problem/11404
이번 문제는 플로이드-워샬(Floyd-Warshall) 문제였습니다.
플로이드-워샬 알고리즘은 모든 정점 간의 최단 경로를 구하는 알고리즘입니다. 😊
《문제 풀이》
1. i == j 이면 0, 아니라면 무한대로 초기화
2. 버스의 정보 입력 (시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c)
3. 플로이드 워샬 알고리즘
--> 정점을 거쳐가는 것이 더 빠르다면 graph[from][to] = graph[from][via] + graph[via][to] 로 갱신
4. i -> j 로 가는 경로가 없다면 해당 값 대신에 "0" 출력
《C++ 코드》
#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
int n, m;
int graph[101][101];
// i->i 로 가는 경로는 0
void initial() {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
graph[i][j] = i == j ? 0 : INF;
}
void floyd() {
// 정점을 거쳐가는 것이 더 빠르다면 갱신
for(int via=1; via<=n; via++)
for(int from=1; from<=n; from++)
for(int to=1; to<=n; to++)
graph[from][to] = min(graph[from][to], graph[from][via] + graph[via][to]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
initial();
for(int i=0; i<m; i++) {
int a, b, c;
cin>>a>>b>>c;
graph[a][b] = min(graph[a][b], c);
}
floyd(); // 플로이드-워샬
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
// i->j 경로가 없으면
if(graph[i][j] == INF)
cout<<"0"<<" ";
else
cout<<graph[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
개발 환경: Dev-C++
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 12852번 1로 만들기 2 (0) | 2021.03.01 |
---|---|
백준 2263번 트리의 순회 (0) | 2021.02.25 |
백준 11779번 최소비용 구하기 2 (0) | 2021.02.17 |
백준 9935번 문자열 폭발 (0) | 2021.02.15 |
백준 14983번 서강그라운드 (0) | 2021.02.12 |