다익스트라
-
다익스트라 알고리즘은 이렇게 쓰는 게 맞다!알고리즘 2023. 8. 18. 02:22
최단 경로 알고리즘 문제를 풀기 위해, 처음 다익스트라 알고리즘을 공부하면서 너무 헷갈렸다. 개념 자체는 우선순위 큐를 사용한 BFS이기 때문에 하나도 어렵지 않다. 근데 왜 헷갈렸느냐? 인터넷에는 수많은 버전의 제각기 다른 다익스트라 알고리즘들이 있었다. 알고리즘 문제를 푼 사람들의 코드를 보면, 다들 다익스트라의 개념은 맞지만 조금씩 다르게 구현해서 쓰고 있었다. 그 중에는 쓸데없이 성능상 저하가 있는 코드도 있었고, 이런 특수한 케이스에서는 틀릴 것 같은데? 싶은 코드도 있었다. 따라서 나는 알고리즘 문제를 풀기에 가장 "적합한" 다익스트라 알고리즘의 코드를 만들었다. (내 머리에서 가장 적합하다고 생각한 것이기 때문에, 이보다 더 좋은 구현이 있을 수도 있지만) 다음 블록에 내 다익스트라 알고리즘..