Minimum Path Cost in a Grid

요즘은 하도 백준 문제들만 풀어봤기에 오랜만에 리트코드로 넘어가서 괜찮은 문제가 없나 보던 와중에 재밌어 보이는 문제를 한번 풀어보았다.

솔직히 설명 자체는 정말 어질 어질 하기때문에 몇번씩 다시 읽어보고 예시 또한 몇번씩 봤어야지 이해를 했던 문제였다. 첫번째 예시에서 나와있는 그림처럼 노드 하나에서 이동 할수있는 공간은 그 다음층에 있는 하위 노드들 이다. 하위 노드로 이동할때마다 moveCost 에서 움직이는 값을 지불해야 하고 첫번째층에 있는 아무 노드에서 시작해서 마지막 노드에 닿는 가장 짧은 moveCost 를 리턴하면 되는 문제이다.

이 문제는 사실 Top-Down 혹은 Bottom-Up 의 DP 방식으로 풀어도 되지만 사실 다익스트라의 알고리즘을 이용해서 푸는것도 하나의 방법이다. 이런 Shortest Path 문제들을 접한게 좀 오랜만이여서 그런지 뭔지 이 문제를 처음 내 힘으로 풀었을때 너무 어이없게 TLE 가 나와 이유를 보니 내가 큐 구조를 안썼다는거다.

정말 어이없지 않은가..다익스트라에서 큐를 안쓰고 풀려고 했단게...

로직은 분명히 맞았지만 그냥 pq 구조를 쓰면서 shortest distance 를 안찾았기 때문에 이 문제는 틀렸다. 그리고 다시 다익스트라 알고리즘의 개념을 바로 잡은 뒤 풀어봤는데 꽤 쉬운 구조였다.

다만 여기서 제일 중요 했던 거는 계산 과정이었는데 계산을 좀 무지성으로 실수하게 되면은 틀린 답이 나오기때문에 해당 값을 계산 하는 방식에 더 신경을 써야했었다. 앞으로 DFS, BFS, Shortest Distance 등등 정말 다 풀어봐야곘다.

배운점:
1. 다 안다고 자만하지말자
2. 꾸준한 탐색 문제 연습