ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1753
    알고리즘/acmicpc 2015. 7. 1. 19:41

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

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


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

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


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


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

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


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

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

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


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


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

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


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

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


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

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


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


    겸손해야지


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

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

    댓글

Designed by Tistory.