반응형
문제
https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
풀이
음의 간선이 있기 때문에 다익스트라 알고리즘으로는 풀이할 수 없습니다.
벨만-포드 알고리즘을 사용해서 풀 수 있습니다.
n - 1 번 반복하여, 모든 간선에 대해 경로를 최소값으로 갱신이 가능한지 확인해준다면 음의 간선이 있어도 최단 경로를 구할 수 있습니다.
n - 1 번 반복한 후, 한 번 더 최소값으로 갱신이 가능하다면, 음의 싸이클이 있는 경우입니다.
소스코드
후기
가장 기본적인 벨만-포드 알고리즘을 묻는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 1956 운동 (Swift) (0) | 2023.04.28 |
|---|---|
| [BOJ] 백준 11404 플로이드 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 13549 숨바꼭질 3 (Swift) (0) | 2023.04.27 |
| [BOJ] 백준 1504 특정한 최단 경로 (Swift) (0) | 2023.04.27 |
| [BOJ] 백준 1753 최단경로 (Swift) (0) | 2023.04.27 |
