https://www.acmicpc.net/problem/11404
걸린 시간 : 12분 50초 (이에 해당하는 강의를 본 직후 풀어서 시간은 의미 없음)
플로이드 와샬 알고리즘의 가장 기본이 되는 문제이다.
플로이드 알고리즘은 임의의 점부터 임의의 점까지의 모든 최단거리를 알고 싶을 때 사용하는 O(N^3) 알고리즘이다. N이 몇백 수준일 때 사용하면 된다. 1000이 넘어가는 시점부터는 다익스트라 등 다른 알고리즘을 사용할 수 있는지 확인하자.
알고리즘
플로이드 알고리즘은 생각해내긴 어렵지만 구현하기는 너무 쉬운 알고리즘이다. 왜 그렇게 되는지는 직접 랜덤한 그래프를 그려보고, 실제 코드를 따라 해보면 단번에 이해가 갈 것이다.
그래프를 인접행렬의 형태로 dist 라는 배열에 넣는다. 초기화는 평소와 같이 해준다. (경로가 없을 땐 INF, 자기 자신일 땐 0)
이제 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 라는 식을 3중 for문을 통해 실행하면 된다. 현재 값과 다른 지점을 거쳐갈 때 중 작은 값으로 최신화해주는 것이다. for문의 순서는 k → i → j 이다.
정답코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dist[101][101];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < 101; i++)
fill(dist[i], dist[i]+101, 987654321);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c);
}
for (int i = 1; i <= n; i++)
dist[i][i] = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == 987654321)
cout << "0 ";
else
cout << dist[i][j] << " ";
}
cout << "\n";
}
return 0;
}
'Baekjoon Online Judge' 카테고리의 다른 글
[BOJ] 1941: 소문난 칠공주 (Java) with 조합 (0) | 2023.10.19 |
---|---|
[BOJ] 1520 : 내리막 길 (C++) with Top Down DP (1) | 2023.10.05 |
[BOJ] 14501 : 퇴사 (C++) with DP (1) | 2023.09.27 |
[BOJ] 20056: 마법사 상어와 파이어볼 (C++) (1) | 2023.09.27 |
[BOJ] 17828 : 문자열 화폐 (C++) (0) | 2023.09.21 |