[백준] 플로이드 : 11404 Python

플로이드 와샬 알고리즘을 공부하면서, 백준에서 플로이드-와샬의 기본 문제를 풀어보았다.

처음 플로이드 와샬 알고리즘을 들어보았을 때 엄청 어려운 알고리즘일거같다고 느꼈지만 막상 코드 자체는 그리 복잡하지 않았다. 

다익스트라처럼 최단거리를 알려주는 알고리즘인데, 다익스트라는 한점에서 다른 한 점까지의 최단거리를 구하는 알고리즘이지만 플로이드는 모든 점에서 모든 점까지의 최단거리를 알 수 있다. 또 다른 차이점은 플로이드는 이전에 구한 최소비용과 새로 구한 최소비용을 비교하면서 갱신하는 DP형태의 알고리즘이라면, 다익스트라 알고리즘은 최소비용인 경우만 갱신하는 그리디 형태의 알고리즘이다. ( 플로이드 알고리즘을 공부하면서 내가 아직 다익스트라와 힙 자료구조에 대해서도 공부가 부족함을 깨달았다.)

플로이드 와샬 알고리즘은 https://freedeveloper.tistory.com/277?category=888096 이 블로그에서 아주 잘 설명해 주었기 때문에 이 블로그를 참조한다면 될것이다.

문제는 이름부터 플로이드다. n개의 도시가 있을 때 각 도시에서 다른 도시로 갈 때의 최소 비용을 구하는 문제이다.

플로이드 문제풀이

코드를 보면 이렇게 되는데, 알고리즘 부분에 대해서 간략하게 설명하자면, K는 어떤 경로를 통해서 갈지 경우의 수이고, S는 시작 도시, E는 도착 도시가 된다. 

결국 K에 따라 출발 도시에서 바로 목적 도시로 가는 게 빠른지, K도시를 거쳐서 목적도시로 가는게 빠른지 배열에 최적의 값을 기록해 나가며 비교하는 과정을 거친다. 이 과정을 모두 거치면 배열에는 각도시에서 각도시로 가는 최단 거리만 남게 된다.

생각보다 알고리즘이 심플하고 편해서 놀랐지만, 경우에 따라서는 다익스트라와 힙을 쓰는 게 훨씬 성능이 좋은 경우가 많았다. 플로이드를 공부하면서 다익스트라부터 먼저 익히고 플로이드로 넘어와야겠다고 크게 느꼈고, 내일부터는 힙부터 공부할 것 같다...

문제출처 : 백준 https://www.acmicpc.net/problem/11404

11404번: 플로이드