codingturtles   13일 전

이동거리 = 옮겨 다닌 하이퍼튜브 수

방문한 마을의 수 : '이동거리 + 2(처음마을,마지막마을)'로 가정하여 최단거리를 구하는 문제라고 생각해 다익스트라를 이용하여 구하여보았습니다.

  • 동일한 하이퍼튜브 내 이동한다면 : 이동거리 0
  • 다른 하이퍼튜브를 이용해 이동한다면 : 이동거리 1

주어진 예제를 통해 예시를 든다면

1->9로 이동하는 방법은 1->2->3->6->8->9 경로로 이동할 수 있습니다.

(1) 1->2->3 : 동일한 1번 하이퍼튜브 이용 : 이동거리 0

(2) 3->6 : 1번 하이퍼튜브에서 3번 하이퍼튜브로 이동해 6번 마을로 감 : 이동거리 1

(3) 6->8->9: 3번 하이퍼튜브에서 5번 하이퍼튜브로 이동해 9번 마을에 최종 도착: 이동거리 1

따라서 방문한 마을의 수 = 2 + 2 (이동거리 + 처음마을 + 마지막 마을) = 4


이 방식은 결국 틀리게 되어 다른 방법으로 풀어보려고 하지만

제가 생각한 방법에 어떤 문제점이 존재하는지 궁금해서 질문 남깁니다.

댓글을 작성하려면 로그인해야 합니다.