하루 세 가지의 주제를 골라 문제를 풀어봅시다.
자료구조
플로이드 - 와샬
- 문제 : 우주 탐사선
- 난이도 : Gold 2
- 해설
- 해당 문제는 모든 정점에서 다른 모든 정점으로의 최단 거리를 구하는 플로이드-와샬 알고리즘을 사용하면 끝나겠구나 생각했지만 다른 문제가 남아있었습니다.
- 플로이드-와샬 알고리즘을 사용할 수 있다는 것은 알고리즘의 시간복잡도가 O(n^3)인데 n이 10이하이므로 가능하다는 것을 알 수 있었습니다.
- 다음으로 필요했던 것은 행성간의 탐사 순서를 모두 구할 수 있는 것이 중요했습니다. 모든 탐사 순서를 구하는 이유는 모든 탐사 가능 순서를 구해야 가능한 최단 시간을 구할 수 있기 때문입니다.
- 순열을 이용해서 가능한 모든 탐사 순서를 구한 뒤 모든 탐사 순서에 대한 총 탐사 시간을 구하면 최소 탐사 시간을 구할 수 있을 것 입니다.
- 소스 코드 : https://www.acmicpc.net/source/30536700
벨만-포드