백준 - 1520 내리막 길 [DP]

 

1520번: 내리막 길

 

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. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/1520.%E2%80%85%EB%82%B4%EB%A6%AC%EB%A7%89%E2%80%85%EA%B8%B8