tony9402
[ADD] 2660 python solution
다익스트라로 풀이했습니다. start 노드로부터 모든 노드까지의 최단경로를 조사해서 그 중 가장 큰 값이 start 노드의 점수가 됩니다. 해당 점수가 가장 낮은 노드를 골라야 하므로 반복문을 노드 수만큼 돌면서 다익스트라 함수를 실행합니다.
BFS를 해도 되는데 dijkstra를 써서 보류하겠습니다
레포지토리에 최단경로로 분리되어 있어서 다익스트라로 풀이한 것입니다
간선 가중치가 1인 이런 문제들의 경우 BFS로도 최단경로를 구할 수 있고 그게 더 효율적이어서 개인적으로는 보류하였는데, 다른 reviewer분들의 의견이 궁금하네요.
특정 점에서의 특정 점까지의 최단 거리를 구하는 알고리즘을 dijkstra라고 하니, 최종적으로는 동일하지 않을까 싶네요. 그런데 저는 이 문제 모든 정점의 페어에 대한 최단거리를 구해야하니 floyd-warshall 로 푸는게 깔끔하다고 생각합니다.
특정 점에서의 특정 점까지의 최단 거리를 구하는 알고리즘을 dijkstra라고 하니, 최종적으로는 동일하지 않을까 싶네요. 그런데 저는 이 문제 모든 정점의 페어에 대한 최단거리를 구해야하니 floyd-warshall 로 푸는게 깔끔하다고 생각합니다.
- dijkstra는 그냥 최단경로 알고리즘 중에 하나일 뿐이고, 현재 코드는 불필요한 연산을 하고 있기 때문에 시간복잡도 상으로 동일하지 않습니다. (현재 코드에서 priority queue 대신 그냥 queue로 바꾸면 동일해집니다.)
- 저도 floyd-warshall이 더 깔끔하다고 생각은 하는데, 현재 코드에서 BFS쪽이 수정이 덜 필요할 것 같아 comment 남겼습니다.
안녕하세요.
새로운 https://github.com/tony9402/algorithm-solutions 레포에 같은 풀이가 존재하지 않는다면 다시 솔루션을 올려주시면 감사하겠습니다.
