이런식의 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년 전
처음에 이 문제를 풀때 우선순위 큐를 이용해서 다익스트라 방식으로 문제를 해결하기 위해 작성을 하였는데
시간초과가 떴습니다. 그 이유를 생각해보니 정점의 개수와 간선의 개수를 곱했을 때의 큰 값때문에 시간 초과가 났다고 가정을하고
실제로 풀었던 분들의 해결방법을 보았더니 포장할 수 있는 개수를 dist에 추가해서 2차원 배열로 해결하는 것을 알게 되었습니다.
제가 궁금한 점은 두가지인데
1. 아래의 1번 소스처럼 우선순위 큐로만 문제를 풀게되면 시간 복잡도가 O(n*m)가 맞는지
2.아래의 2번 소스처럼 우선순위큐에 포장할 수 있는 개수를 추가한 2차원 배열의 dist는 정확히 시간 복잡도가 얼마나 향상되는건지 (if문의 조건식이 중요한건지, 실제로 2번소스는 시간초과 없이 통과하였습니다)
고수님들 답변부탁드립니다.. 이와 관련하여 저와 같은 생각을 가진 분들도 자유롭게 의견공유해도 좋습니다!!