백준 1916번 최소비용 구하기 풀이/해설/코드 (파이썬) 다익스트라 알고리즘 활용하기!

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

 

전에 다익스트라 알고리즘을 접해본 적이 있어서, 딱 보자마자 다익스트라구나..햇던 문제이다. 내가 처음 코딩테스트를 준비하면서 샀던 책이 파이썬 알고리즘 인터뷰인데 해당 문제는 41번에 있다. 별개의 이야기이긴 하지만 정말 추천하는 책이기 때문에 코딩테스트를 처음 준비하는 사람들에게 추천한다. 깃허브에 코드가 올라와있어서 해볼 수도 있다.

GitHub - onlybooks/algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는

 

아무튼 그래서 내가 처음 다익스트라 알고리즘을 접한 경로가 위 책이다 보니 계속 위 책처럼 풀이를 하게되는데, 이번 문제도 이렇게 풀었더니 메모리 초과 오류가 떴다. 내가 처음 풀었던 논리는 이렇다.

 

1. 각 노드를 방문할 때마다 해당 노드에서 갈 수 있는 다른 노드 + 그 때의 비용을 스택에 저장한다.

2. 스택에서 비용이 낮은 순서로 꺼내서 그 노드를 방문하고 1을 반복한다.

 

그리고 이 경우 메모리 초과가 나는 이유는, 내 생각에는 아마도 노드를 한번 방문 할 때마다 그 인접 노드들을 모두 스택에 넣기만 하고 visited표시하지 않기 때문인 듯 하다. 이런식으로 하면 stack에서 한번 노드를 꺼낼 때마다 딱 하나의 노드만 방문하면서도 그 노드의 인접노드는 모두 스택에 넣어야하기때문에 스택에 중복된 노드가 들어갈 경우가 굉장히 커진다. 그리고 수정한 로직은,

 

1. 각 노드를 방문할 때마다 해당 노드의 인접 노드도 visited에 표시하고 현재의 비용을 같이 저장해두면서 스택에도 같이 넣는다.

2. 스택에서 비용이 낮은 순서로 꺼내서 그 노드의 인접 노드들을 방문하는데, 전에 저장했던 비용보다 낮은 경우에 대해서만 1번을 반복한다.

 

첫번째 로직에서도 방문하지 않은 경우에만 for문을 해서 인접노드를 방문하는 식으로 진행할 수는 있긴 하지만 그렇다고 해도 이미 근접노드를 방문처리해놓고 그것보다 작은 경우에만 스택을 추가하는것과 비교한다면 상대적으로 첫번째 로직에서는 스택에 더 많은, 더 많이 중복된 노드들을 넣을 수밖에 없게 된다.