반응형
문제
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
풀이
문제명 처럼 모든 노드에서 최소한의 거리를 구하는 플로이드 워셜 알고리즘으로 풀이할 수 있는 문제입니다.
플로이드 워셜 알고리즘의 기본만 작성하면 풀이할 수 있는 문제입니다.
단 한가지에 주의해야 하는데, 시작 도시와 도착 도시를 연결하는 노선이 1개가 아닐 수 있기 때문에,
비용을 저장할 때, 비용이 가장 작은 비용으로 저장해주어야 합니다.
소스코드
후기
다익스트라, 벨만포드 보다는 플로이드워셜 알고리즘이 이해하기에 더 쉬웠습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 3273 두 수의 합 (Swift) (0) | 2023.04.28 |
|---|---|
| [BOJ] 백준 1956 운동 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 11657 타임머신 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 13549 숨바꼭질 3 (Swift) (0) | 2023.04.27 |
| [BOJ] 백준 1504 특정한 최단 경로 (Swift) (0) | 2023.04.27 |
