lmcoa15   6년 전

처음에 이 문제를 풀때 우선순위 큐를 이용해서 다익스트라 방식으로 문제를 해결하기 위해 작성을 하였는데

시간초과가 떴습니다. 그 이유를 생각해보니 정점의 개수와 간선의 개수를 곱했을 때의 큰 값때문에 시간 초과가 났다고 가정을하고

실제로 풀었던 분들의 해결방법을 보았더니 포장할 수 있는 개수를 dist에 추가해서 2차원 배열로 해결하는 것을 알게 되었습니다.

제가 궁금한 점은 두가지인데 

1. 아래의 1번 소스처럼 우선순위 큐로만 문제를 풀게되면 시간 복잡도가 O(n*m)가 맞는지

2.아래의 2번 소스처럼 우선순위큐에 포장할 수 있는 개수를 추가한 2차원 배열의 dist는 정확히 시간 복잡도가 얼마나 향상되는건지 (if문의 조건식이 중요한건지, 실제로 2번소스는 시간초과 없이 통과하였습니다)


고수님들 답변부탁드립니다.. 이와 관련하여 저와 같은 생각을 가진 분들도 자유롭게 의견공유해도 좋습니다!! 

yukariko   6년 전

이런식의 2차원 배열로 다익스트라 하는것은 정점의 확장으로 이해하시면 편할것 같습니다.

정점의 개념이 도시를 의미하는 N개의 정점에서

0개의 도로포장 상태의 도시 N, 1개의 도로포장 상태의 도시 N ... K개의 도로포장 상태의 도시 N개로

총 KN개의 정점이 있다고 생각하시면 됩니다.

간선도 Ku Nu 정점에서 Ku + 1 Nv 로 가는 정점 또는 Ku Nu -> Ku Nv 로 가는 정점이 있다고 생각하면

다익스트라 알고리즘으로 해결할 수 있습니다.

따라서 시간복잡도 또한 다익스트라의 시간복잡도와 같은 O(VlgE) = O(VlgV) 가 됩니다.

정점이 KN개로 확장되었으므로 시간복잡도는 O(KNlg(KN))이 되겠습니다.

lmcoa15   6년 전

댓글 남겨주신것을 계속해서 보고 생각을 했습니다..우선 댓글을 달아주셔서 너무 감사드립니다!!


보면서 조금 헷갈렸던 부분이 있는데 정점의 개수가 KN개로 확장되면서 시간복잡도가  O(KNlg(KN)) 이 되었다고 하셨는데

혹시 시간복잡도에 lg(KN)을 곱한 이유가 우선순위큐를 이용하였기 때문인가요??.. 우선순위큐가 힙을 이용한 것으로 알고있는데 힙의 시간복잡도가 정점의 개수가

N개 일때 O(Nlg(N))인 것으로 알고있는데 이것이 맞는지 궁금합니다!!


그리고 위의 1번소스에서 도로 포장의 개수인 K를 따로 생각하지않고 while문에서 도로포장의 개수인 k가 되기전까지 도로 포장을 하지 않은것과 도로 포장을 한 것을

계속해서 큐에 삽입하였는데 이때의 시간복잡도가 O(NM*lg(NM))이여서 시간초과가 나는것이 맞는지 궁금합니다!!

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