[ 2021.07.01 ] 하루 세 문제

정유택·2021년 7월 2일
0

everyday_algorithm

목록 보기
8/8

하루 세 가지의 주제를 골라 문제를 풀어봅시다.

  • 자료구조
  • 플로이드-와샬
  • 벨만-포드

자료구조

플로이드 - 와샬

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

벨만-포드

0개의 댓글