inu_study   8달 전

 처음에 풀었을때는 그래프 경로 탐색 알고리즘을 DFS로 구성했는데.. 시간초과가 계속나서 다른게 있나 생각을 했습니다.

그러다가 다익스트라를 알게돼서 다익스트라로 다시 구성했는데도 시간초과가 뜨네요 ㅠㅠ..

for문돌려서 정점 1000개, 도로 1000*999/2 개로 돌려보니 DFS는 50초대 나오고, 다익스트라는 20초 나왔습니다.

확실히 효울은 더 나은데.. 그래도 시간초과가 뜨니 답답합니다.. 아예 틀린 걸까요..? 도와주세요 ...ㅠ

f52985   8달 전

작성하신 다익스트라 알고리즘은 O(V^2)짜리 알고리즘입니다. 하지만 본 문제를 해결하기 위해서는 우선순위 큐 등을 사용한 더욱 효율적으로 개선된 다익스트라 알고리즘을 사용해야 합니다. 

inu_study   8달 전

아.. 역시 알고리즘 효율성이 문제였군요.. 큐를 힙으로 구성해서 다시 도전해봐야 겠습니다.. 감사합니다 ^^..

댓글을 작성하려면 로그인해야 합니다.