우주 탐사선
-
[Python] 백준 17182 우주 탐사선알고리즘/문제풀이 2021. 8. 7. 18:44
1. 문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 2. 문제 요약 모든 행성을 탐사하기 위한 최소 시간을 출력한다. 3. 아이디어 정리 플로이드 와샬. 모든 정점 최단 거리 구하기 행성을 백트래킹으로 탐색하여 모든 행성 방문하여 최소 시간 구하기 참고 - 플로이드와샬 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 플로이드 워셜 점화식 각 단계마다 특정한 노드 k를 거쳐 ..