입력 크기가 작아서 그런 것 같습니다. 이 문제로 비교해 보세요.

https://www.acmicpc.net/proble...

그냥 큐로도 풀린다면 데이터를 추가해야 되는 것 아닌가요? 아 아니면, 이 방법은 중복 방문을 감행하면서 업데이트 시마다 큐에 추가하며 진행해서 풀린 걸까요?

도시가 1000개라서 상관 없는 거 같아요.

그냥 인접 행렬로 저장해도 뭐..

제가 봤을 때에는.. 도시 수에 비해서, 길의 수가 상당히 커서 그런 결과가 나오지 않았나 싶기도 하네요.

일단.. 우선순위 큐 같은 경우에는.. 빼는 연산도 있겠지만 넣는 연산도 O(log(현재 우선순위 큐 사이즈))라서..

정점 갯수가 V이고 간선 갯수가 E일 때 다익스트라의 복잡도가 O(ElogV)가 되고요. 그냥 일반적인 다익스트라가 O(V^2) 정도 되는데요.

10만 * log1000하고 1000 * 1000이 거의 같으니..

인접 행렬은 별개의 문제인 것 같고요, 제가 볼 때 여기서의 요점은 "거리가 갱신될 때마다 큐에 항상 삽입"함으로써 문제를 해결했다는 점인 거 같네요.

원래 다익스트라 알고리즘은 모두 우선순위 큐에 넣어놓고 거리가 갱신될 때마다 값만 수정한 뒤에, 그 때까지 최소거리인 정점을 pop하고 그 정점까지의 거리를 확정짓는 방식인데요, 이 코드상으로는 큐에 여러 번 넣는 것을 막을 장치도 없고, 다만 거리가 최소가 될때까지 무한정 큐에 다시 넣을 수 있으니 결과적으로 올바른 결과가 도출되는 게 아닌가 싶네요.

다만 이 경우 큐에 여러 번 노드가 들어가는 것을 감수해야 하니 그만큼 시간복잡도는 증가할 거라고 생각되네요. 더 큰 케이스로 시도하면 시간이 많이 걸릴 수도 있다고 생각해요. 이건 queue를 쓰느냐 priority_queue를 쓰느냐의 문제보다도, "중간에 정점의 거리가 수정될 때 큐에 또 넣느냐 안 넣느냐"의 차이인 것 같아요.

그래서 다익스트라를 처음 배울 때 저는 heap에서 중간의 원소를 변경했을 때의 동작을 같이 배웠었는데요, priority_queue에서는 이 동작이 지원되지 않기 때문에 set에서 기존의 노드를 찾아서 지우고 다시 삽입하는 식으로 해야 한다고 들었고요.

흐음.. c++에서 우선순위 큐가 그렇게 동작하는 모양이군요..

한 번 찾아봐야겠네요.

그런데. 제가 PQ를 구현할 때도

중간에 정점의 거리가 수정될 때 큐에 또 넣어버립니다..

c로 직접 구현하면 정점 거리가 수정될 때

그 위치를 찾아서, 변경 연산을 수행할 수는 있긴 하더라고요. 위치가 있는가 없는가는..

현재 loc 위치의 최단 거리가 저장되어 있는 자식 번호를 저장하는 배열을 만들어서 관리하면 되니까요.

어짜피 거리가 짧아지기 때문에

우선순위를 올리거나, 아니면 가만히 있게 하느냐. 만 생각하면 되거든요.

문제를 알았습니다.

저렇게 PQ를 사용하면 정점의 번호 순서대로 우선순위가 결정됩니다.

거리를 기준으로 우선순위가 결정되야 되는데 말이죠