priority
-
[BOJ] 1520번 내리막 길Algorithm/BOJ 2022. 6. 10. 13:07
[BOJ] 1520번 내리막 길 처음에는 DP와 BFS로 푸는 문제로 접근하였다. 생각하였던 예시 중에서는 올바르게 동작하였으나, 제출 시 시간 초과가 걸려 실패하였다. 왜 그런지 곰곰히 생각해보던 도중 BFS로 구현을 하게 되면 순차적으로 탐색을 하게 되어 돌아서 가는 경우에 대해서 갱신하여 처리하기 어렵다. 따라서 어차피 숫자 가중치에 따라 더 큰것부터 우선으로 찾아 들어가야하기 때문에 BFS의 Queue를 우선순위 Queue로 구현해볼까라고 생각하였다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는..