silvanas   2년 전

항상 수고가 많으십니다.

문제를 어떻게 풀어야할지는 대충 캐치를 했습니다.

근데 더이상 어떻게 시간을 줄여야할지 잘 모르겠습니다.

짚이는 부분이 있긴한데 

예를 들면 노드를 방문할때 1->2->1->2 식의 중복된 노드 방문이 문제인것같습니다만..

이걸 어떻게 극복해야할지 모르겠습니다.

혹은 다른문제가 있을수도있지만요. 조언 부탁드리겠습니다 !

다익스트라 알고리즘으로 구현하였습니다.

kajebiii   2년 전

인접리스트가 아닌 인접행렬을 쓰셔서

지금 최악의 경우 총 N*N 번 다익스트라의 while루프를 돌게 되는데, 그때마다 N번 for문을 돌게 됩니다.

즉, 시간복잡도가 최악의 경우 O(N^3)가 됩니다.

인접행렬이 아닌 인접리스트를 쓰시면 O(NM)으로 바뀌게 됩니다.

바뀌게 되는 이유는 생각해 보시길 바래요.

silvanas   2년 전

읽기 난해한 부분이 있어서 조금 고쳐서 다시올립니다.

안그래도 그 방법 밖에 없다고 생각하여

인접 리스트로 바꾸어 보았는데

런타임 오류가 나네요.

읽어주셔서 감사합니다.

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