5214번 - 환승
이동거리 = 옮겨 다닌 하이퍼튜브 수
방문한 마을의 수 : '이동거리 + 2(처음마을,마지막마을)'로 가정하여 최단거리를 구하는 문제라고 생각해 다익스트라를 이용하여 구하여보았습니다.
주어진 예제를 통해 예시를 든다면
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
이 방식은 결국 틀리게 되어 다른 방법으로 풀어보려고 하지만
제가 생각한 방법에 어떤 문제점이 존재하는지 궁금해서 질문 남깁니다.
댓글을 작성하려면 로그인해야 합니다.
codingturtles 2년 전
이동거리 = 옮겨 다닌 하이퍼튜브 수
방문한 마을의 수 : '이동거리 + 2(처음마을,마지막마을)'로 가정하여 최단거리를 구하는 문제라고 생각해 다익스트라를 이용하여 구하여보았습니다.
주어진 예제를 통해 예시를 든다면
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
이 방식은 결국 틀리게 되어 다른 방법으로 풀어보려고 하지만
제가 생각한 방법에 어떤 문제점이 존재하는지 궁금해서 질문 남깁니다.