1753번 - 최단경로
제목 그대로 우선순위 큐(=최소힙)을 구현한 후 dijkstra 를 적용해서 게시판 내의 반례들을 모두 풀었습니다.
한 70% 쯤 넘어가더니 시간초과가 뜨네요.. ㅠㅠ
주석문 달아놓은 부분이 문제인 거 같은데
dijkstra 에서 이미 방문한 노드라도 값이 갱신되면 재방문하는 방식으로 코드를 짰는데 이 부분을 구현한 후 시간 초과가 발생했습니다..
다시 방문하는 조건이 틀린 걸까요..?
다익스트라 알고리즘은 우선순위 큐를 써서 거리가 짧은 순으로 방문하기 때문에 한 번 방문한 정점을 다시 방문했을 때 인접한 정점의 거리를 더 짧게 갱신할 가능성이 없고, 다시 방문했을 때는 인접 정점을 순회하지 않아도 괜찮습니다. 이러한 재방문은 최악의 경우 V^2번 연산을 필요로 하게 만들어 시간 초과를 받는 것 같습니다.
감사합니다. 하나씩 그려보면서 확인했더니 인접한 거리를 더 짧게 갱신하는 일이 없네요.
덕분에 해결했습니다. ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
alsrb0504 2년 전
제목 그대로 우선순위 큐(=최소힙)을 구현한 후 dijkstra 를 적용해서 게시판 내의 반례들을 모두 풀었습니다.
한 70% 쯤 넘어가더니 시간초과가 뜨네요.. ㅠㅠ
주석문 달아놓은 부분이 문제인 거 같은데
dijkstra 에서 이미 방문한 노드라도 값이 갱신되면 재방문하는 방식으로 코드를 짰는데 이 부분을 구현한 후 시간 초과가 발생했습니다..
다시 방문하는 조건이 틀린 걸까요..?