[최단 경로] [Python / C++] 1956. 운동 - GOLD Ⅳ

본 게시글은 PC버전에 최적화 되어있습니다.

 

1956번: 운동

 

 

입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

---

해결 방법

우선 다른 최단 경로 문제와 약간 다를 수 있다.

지금까지의 최단 경로 문제는 특정 지점까지의 최단 경로, 혹은 다른 지점을 거쳐서 특정 지점까지의 최단 경로였다면

이번에는 사이클이 있는 경로 중 최단 경로를 탐색하는 것이 핵심이다.

 

사이클? 처음에는 벨만 포드 문제인 줄 알았다.

하지만 도로 길이가 음수가 주어지지 않은 것을 보고 다익스트라로 다시 바로잡고 해결하려고 했다.

 

나는 우선 내가 지금까지 최단 경로 문제를 접할 때 구현했던 방식으로 똑같이 다익스트라를 구현했다.

 

아래 링크를 참고하면 구현했던 다익스트라 코드를 볼 수 있다.

github.com/k906506/Algorithm/blob/master/3.%20Dijkstra.py

k906506/Algorithm

 

그렇게 구현하고 해결하려는데 이 방법으론 해결할 수 없음을 깨달았다.... ㅠ

우선 문제를 제대로 이해할 필요가 있었다.

주어진 입력 값은 3을 출력하는데 아래와 같은 구간이 정답이므로 3이 출력되는 것이다.

 

정리해보자면 모든 정점을 시작 지점으로 잡고 다익스트라로 탐색하면서

시작 지점에 저장된 거리 중 가장 짧은 거리를 출력하면 되는 문제였다. (플루이드 와샬...?)

 

아직까지 이해가 안될 수 있으니 왜 시작 지점에 저장된 가장 짧은 거리가 정답이 되는지 모를 수 있다.

그 이유는 간단하다. 문제에서 원하는 것은 시작 지점으로 되돌아올 수 있는 거리 중 가장 짧은 거리.

심지어 그래프도 단방향으로 주어졌기 때문에 시작 지점으로 돌아올 수 있어야한다.

 

정리해보자면

1. 시작 지점으로 되돌아올 수 있어야한다.

2. 시작 지점으로 되돌아올 수 있는 거리 중 가장 짧은 거리.

 

아무튼 이해를 제대로 하고 다시 다익스트라 코드를 봤는데 다익스트라를 실행하는 부분에서

시작지점의 distance를 무조건 0으로 초기화해주는 과정이 있어서 정상적으로 출력되지 않는 것이였다!

 

위에 주석 처리한 부분을 지워줬다.

최종적으로 모든 정점에 대해 탐색 과정을 반복하면서 가장 짧은 거리를 출력하면 된다.

 

아래 출력문은 위에서부터 차례대로 1번 정점 ~ 3번 정점을 시작 정점으로 주었을 때의 distance이다.

Index 1부터 보시길.

1번 정점이 시작 정점인 경우 다시 돌아올 수 없으므로 Fail

2번 정점이 시작 정점인 경우 3으로 갔다가 다시 2로 돌아오는 경우이므로 3

3번 정점이 시작 정점인 경우 2로 갔다가 다시 3으로 돌아오는 경우이므로 3

따라서 정답은 3이 된다.

 

엄청난 도전... 파이썬으로는 통과를 할 수 없었다.

파이썬으로 구현한 코드이다.

 

 

C++로 구현한 코드이다.

 

 

다익스트라에 대한 고정관념을 깬 문제였다.

지금까지 무조건 시작 정점의 distance를 0으로 잡고 문제를 해결했었는데 이 문제를 통해 다른 시각을 가질 수 있었다.

내일은 이전 문제인 KCM-Travel에 대한 풀이를 올려야겠다.

 

단계별로 풀어보기 - 최단 경로 CLEAR!

 

나중에 풀고 보니 다익스트라를 플루이드 와샬처럼 풀었다는 것을 알게 됐다.

그래서 플루이드 와샬로 다시 구현하고 돌려봤더니 통과했다.

심지어 좀 더 빠른 속도로 출력되는 것을 볼 수 있었다.

 

플루이드 와샬로 구현할 때 주의할 점은 반복문 탐색 좌표의 순서이다.

"시작 (i) -> 중간에 거치는 좌표 (j) -> 도착 (k)" 이런 식으로 구현하면 Time Out이 발생할 가능성이 높다.

"시작 (j) -> 중간에 거치는 좌표 (k) -> 도착 (i)" 이런 식으로 구현해야한다.

아래 코드를 참고하면 이해가 쉽게 될 것이다.

 

아래는 플루이드 와샬로 구현한 코드이다.