반응형
문제
https://www.acmicpc.net/problem/1956
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
풀이
합이 가장 작은 사이클을 구하는 문제입니다.
모든 경로를 확인해야 하므로 플로이드 워셜 알고리즘을 사용하여 풀이할 수 있습니다.
사이클이 되는지 여부는 어떻게 알 수 있을까요?
단순히 1 -> 3 으로 갈 수 있고 3 -> 1로 갈 수 있으면 사이클이 된다고 할 수 있습니다.
모든 경로에 대해 사이클이 되는지 확인하고, 가장 작은 값을 출력해주면 됩니다.
모든 경로에서 사이클이 되지 않는다면 -1을 출력해줍시다.
소스코드
후기
모든 경로를 확인해야 한다는 것을 보고 플로이드 워셜 알고리즘을 떠올렸습니다.
또한 사이클을 어떻게 찾아주어야 할 지에 대해 생각을 좀 오래했는데, 정말 단순하게 생각해서 풀 수 있어서..
좀 허무하기도 했습니다..
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 2470 두 용액 (Swift) (0) | 2023.04.30 |
|---|---|
| [BOJ] 백준 3273 두 수의 합 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 11404 플로이드 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 11657 타임머신 (Swift) (0) | 2023.04.28 |
| [BOJ] 백준 13549 숨바꼭질 3 (Swift) (0) | 2023.04.27 |
