[백준] 1520번 내리막 길 (자바 풀이)

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 처음 문제를 봤을 땐 DFS를 사용하면 간단하게 풀릴 것 같았다. 하지만 결과는 시간초과..... 이 문제는 단순히 DFS만을 사용하면 시간초과가 발생한다. DFS와 DP를 섞어서 사용해야 한다. 만약 DFS를 통해 모든 길을 탐색하던 도중 이미 탐색해서 경로를 계산한 좌표를 만난다면 굳이 다시 탐색을 할 필요는 없다. 따라서 이를 미리 저장해놓고 사용하면 된다. 코드 HTML 삽입 ..

원문링크 : [백준] 1520번 내리막 길 (자바 풀이)