1753

알고리즘/acmicpc 2015. 7. 1. 19:41 Posted by 아는 개발자

너무나 당연하게 알고있을 거라 생각했던 다익스트라....

나는 다익스트라 알고리즘이 우선순위을 사용해야 한다는 것을 깜빡하고 있었다.


이 문제는 맨 처음에는 메모리 초과를 어떻게 해결할 것이냐로 속을 썩였었는데

메모리 초과를 해결 한 후에는 나의 다익스트라 알고리즘의 문제때문에 한동안 애를 먹었다..


먼저 메모리 초과를 해결하는 방법부터 설명하면


정점의 개수가 20000개이기 때문에 20000*20000의 배열은 만들 수 없다.

그러므로 간선들만의 집합을 만들어두어야 한다.


이때 특정 정점에서 나오는 간선을 어떻게 indexing하느냐 문제가 있었는데

각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다.

(지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다...)


이제 그에 맞추어서 다익스트라를 적용하면 되는데


나는 너무도 당연하게 다익스트라를 큐를 이용해서 구현하면 될 줄 알았다...

하지만 다익스트라는 우선순위 큐를 이용해서 구현해야 한다.


그 이유는 연결된 노드들 중에서 가장 가까운 점과 연결되어야 하는데 이때 나중에 추가된 점이 먼저 추가된 점보다 더 가까이 있는 경우가 생기기 때문이다.

(설명이 그지같으니 혹시나 이글을 보시는 분은 반드시 책을 참조하시길)


맨날 다익스트라 다익스트라 떠들고다녀서 나 스스로 잘 알고 있을 줄 알았는데

오늘 알고리즘 책을 보고 다시 깨달았다.


역시나 잘 알고 있다고 방심하는 순간 틀리는 것 같다.


겸손해야지


728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26