[BOJ][Python] 백준 9370번 - 미확인 도착지

문제 링크: https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

---

문제 풀이

데이크스트라

 

처음에는 g와 h를 방문 했는지에 따라 처리를 했었다. g-h혹은 h-g를 방문했다고 체크를 하면서 해당 번호에 저장을 했었다. 문제는 가중치가 같은데 하나는 g-h 간선을 방문했고 하나는 방문을 안했다면 덮어질 수도 있다. 이 점까지 체크했고 정답을 확신 했었다. 하지만 이제는 시간 초과가 나기 시작했다. 아무래도 가중치가 같은 값이 수없이 많으면 또 그만큼 돌려야하니깐 시간초과가 일어날 수 밖에 없다. 따라서 가중치도 같으면서 방문했는지에 대한 여부를 동시에 할 순 없을까?

 

바로 g-h 간선의 가중치를 손봐주면 된다. 단 티가 안날 정도로 해줘야한다.

데이크스트라는 시간복잡도를 줄이기 위해서 우선순위 큐를 사용하는데 가중치가 같다면 g-h 간선으로 간 것을 우선순위를 높혀야 한다. g-h 간선을 0.01정도 줄이면 가지 않은 것보다 0.01만큼 차이나기 때문에 g-h 간선을 간 것을 우선처리 하게 된다. 그러면 자연스럽게 중복된 것들을 처리도 할 수 있다. 또한 간선을 지나갔으면 (파이썬 기준으로) 정수 값에서 실수값이 되었으므로 INF가 아니고 타입이 float라면 g-h 간선으로 이동했고 최단거리로 이동했다는 뜻이므로 이 부분만 잘 처리하면 된다.

 

코드