주어진 지도에서 오직 내려가기만 하는 길의 개수를 찾는 문제입니다. 이 문제는 풀이법이 2가지가 있을 수 있는데, priority queue를 기반으로 BFS를 사용하는 방법, DP와 DFS를 사용하는 방법입니다. 저는 전자로 풀었는데 후자로 푸는 것이 정석인 것 같습니다.
먼저 priority queue를 사용하는 방법입니다. 특정 점의 높이와 좌표를 저장하고, 높이에 대한 max-heap인 PQ를 만듭니다. 이제 여기에 시작점 정보를 넣고 다음 점을 찾을 때마다 경우의 수를 합쳐나가면 도착점까지 가는 경우의 수를 찾을 수 있습니다.
두 번째는 DFS / DP를 사용하는 방법입니다. 도착점에서 시작하여 오르막인 점을 DFS로 탐색하면서 해당 점에 시작점으로부터 출발하여 도착하는 가짓수를 저장합니다. 만약 경로가 겹치는 경우 겹치는 구간은 다시 계산할 필요가 없기 때문입니다. 이를 재귀로 돌리면 도착점까지 도착하는 경우의 수를 구할 수 있습니다.
PS알못 OrbitHv의 PS