백준 - 1937 욕심쟁이 판다 [DP]

 

1937번: 욕심쟁이 판다

 

1. 문제 요약

N * N 의 대나무 숲이 주어지고, 해당 숲에는 대나무의 양이 적혀있다.

판다는 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 이동한 곳의 대나무 양은 이전 위치보다 많아야 한다.

판다가 가장 많이 이동할 수 있는 횟수는 몇번인가?

 

2. 접근 방법

• 모든 대나무 숲을 방문합니다.
• 재귀 함수로 구현합니다.

# 재귀함수로 구현
def solution(y, x):
    move = 0

    for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]:
        if 0 <= dy < N and 0 <= dx < N: # 이동할 좌표 범위 제한
            if forest[y][x] < forest[dy][dx]: # 이동할 좌표 선정
                move = max(move, solution(dy, dx) + 1)

    return move

answer = 0
# 모든 칸을 방문
for y in range(N):
    for x in range(N):
        answer = max(answer, solution(y, x))
        
print(answer + 1)

 

• DP 방식으로 변경합니다.

 

3. 파이썬

dp = [[0] * N for _ in range(N)]

def solution(y, x):
    if dp[y][x] != 0:
        return dp[y][x]

    for dy, dx in [[y-1, x], [y+1, x], [y, x-1], [y, x+1]]: #상, 하, 좌, 우
        if 0 <= dy < N and 0 <= dx < N: # 이동할 좌표 범위 제한
            if forest[y][x] < forest[dy][dx]: # 이동할 좌표 선정
                dp[y][x] = max(dp[y][x], solution(dy, dx) + 1)

    return dp[y][x]

for y in range(N):
    for x in range(N):
        solution(y, x)

print(max(map(max, dp)) + 1)

 

4. 자바

static int N;
static int[][] forest;
static int[][] dp;
static int answer = 0;

static private int solution(int y, int x) {
    if (dp[y][x] != 0) {
        return dp[y][x];
    }

    // 상, 하, 좌, 우
    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 < N && 0 <= dx && dx < N) {
            // 대나무 양 검사
            if (forest[y][x] < forest[dy][dx]) {
                dp[y][x] = Math.max(dp[y][x], solution(dy, dx) + 1);
            }
        }
    }

    return dp[y][x];
}

System.out.println(answer + 1);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/1937.%E2%80%85%EC%9A%95%EC%8B%AC%EC%9F%81%EC%9D%B4%E2%80%85%ED%8C%90%EB%8B%A4