개발일지/Algorithm
백준 - 1520 내리막 길 [DP]
E-room
2023. 10. 17. 17:18
728x90
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
1. 문제 요약
M * N 의 지도가 주어지고, 해당 지도에는 각 칸의 높이가 표시되어 있다.
현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 현재 위치보다 낮은 위치로만 이동할 수 있다.
세준이는 0, 0의 위치에서 시작하여 지도의 가장 우측하단까지 이동하는 방법은 모두 몇 가지인가?
2. 접근 방법
- 0, 0 에서 가능한 모든 경우의 수를 탐색합니다.
- 재귀로 구현합니다.
def solution(y, x):
# 목적지 도착 여부
if y == M-1 and x == N-1:
return 1
# 경우의 수
route = 0
# 상, 하, 좌, 우
for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]:
# 이동가능 여부 검사
if 0 <= dy < M and 0 <= dx < N:
if road[y][x] > road[dy][dx]:
route += solution(dy, dx)
return route- DP로 변환합니다.
3. 파이썬
# y, x 에서 0, 0으로 이동할수 있는 모든 경우의 수를 dp에 기록한다
def solution(y, x):
# 목적지 도착 여부
if y == M-1 and x == N-1:
dp[y][x] = 1
return
# 이미 방문한곳
if dp[y][x] != -1:
return
# 방문 표시
dp[y][x] = 0
# 상, 하, 좌, 우
for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]:
# 이동가능 여부 검사
if 0 <= dy < M and 0 <= dx < N:
if road[y][x] > road[dy][dx]:
solution(dy, dx)
dp[y][x] += dp[dy][dx]
4. 자바
static int M;
static int N;
static int[][] road;
static int[][] dp;
private static void solution(int y, int x) {
if (y == M - 1 && x == N - 1) {
dp[y][x] = 1;
return;
}
if (dp[y][x] != -1) {
return;
}
dp[y][x] = 0;
for (int[] temp : new int[][]{{y - 1, x}, {y + 1, x}, {y, x - 1}, {y, x + 1}}) {
int dy = temp[0];
int dx = temp[1];
if (0 <= dy && dy < M && 0 <= dx && dx < N) {
if (road[y][x] > road[dy][dx]) {
solution(dy, dx);
dp[y][x] += dp[dy][dx];
}
}
}
}
5. 전체 코드
728x90