1238번 다익스트라 2회 (1) 썸네일형 리스트형 [백준/Python] 1238번 파티 풀이 문제 해석 문제 풀이 이 문제는 벨만포드 풀이와 다익스트라 풀이가 있으며 다익스트라 2번 만으로도 풀어낼 수 있다. 벨만포드의 경우 C++에서는 통과하였으나 pypy, python 모두 불통과를 받았다... 모든 순서쌍의 거리를 계산하는 방식이니 아래 코드에서만 설명하고 생략하자 다익스트라 2회로 문제를 풀어낼 수 있다는 것이 너무나도 흥미로웠는데 이유는 아래와 같다. 모든 마을(노드)에서 특정 마을로 가는 길(간선)이 존재한다고 하면 간선을 뒤집어서 특정 마을에서 출발하면 모든 마을로 가는 최소 거리를 알 수 있다. (너무나도 충격적인 발상이다..... 대체 뭘 해야 이런 발상이 가능하지) 그리고 기존 순서쌍을 이용해 특정 마을에서 모든 간선으로 돌아가는 거리를 계산하면 총 2번만에 계산할 수 있다. .. 이전 1 다음
