백준 & 프로그래머스
[백준] 1520번: 내리막 길 - 파이썬
hyukji
2023. 1. 5. 20:46
문제보기
https://www.acmicpc.net/problem/1520
1520번: 내리막 길
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.
www.acmicpc.net
풀이 및 코드
필자는 재귀를 이용한 dfs와 dp를 이용해 코드를 구현했다. 먼저 dfs를 통해 길을 찾아가며 dp에 해당 위치에서 도착지점까지 갈 수 있는 경우의 수을 저장했다. dfs나 bfs로만 구현을 하려다가 M, N이 500으로 숫자가 큰 것을 보고 dp를 생각할 수 있었다.