(BOJ)-1937, Python

문제 요약

출처: (BOJ)1937 - 욕심쟁이 판다

$N \times N$ 크기의 대나무 숲이 있고, 각 칸마다 대나무의 양이 주어진다.
특정 칸에 판다를 풀어놓았을 때, 이 판다는 그 칸의 대나무를 모조리 다 먹고, 인접한 칸들 중 방금 먹었던 대나무 양보다 많은 곳만 골라서 먹으러 이동한다고 한다. 이때, 어느 칸에 판다를 풀어 놓아야 판다가 최대한 많은 칸을 방문할 수 있을지를 구하는 문제이다.

• 판다가 처음 풀어질 곳은 아무도 모른다.
• 현재 지점으로부터 상, 하, 좌, 우로만 움직일 수 있다.
• 판다가 처음 풀어진 곳도 카운트 해야 한다.

접근 과정

1. 완전탐색 접근(재귀)

상, 하, 좌, 우 방향으로 이동하는 경우의 수를 쪼개어 처리할 수 있기 때문에, 재귀를 활용하여 접근하기로 했다. 하지만 결과는 예상대로 시간 초과였다.

코드 구현

import sys
sys.setrecursionlimit(400000)

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0

def recursion(y, x, count): 
    global answer
    
    for mv_y, mv_x in [[-1, 0], [1, 0], [0, -1], [0, 1]]: 
        dy, dx = y + mv_y, x + mv_x
        if 0 <= dy < N and 0 <= dx < N:
            if graph[dy][dx] > graph[y][x]: 
                recursion(dy, dx, count + 1)
    answer = max(answer, count)

for init_y in range(N):
    for init_x in range(N):
        recursion(init_y, init_x, 1)       
print(answer)

2. DP 접근(메모이제이션)

이번 문제도 역시 재귀 코드를 바탕으로 DP(메모이제이션) 으로 접근하였고, 결과는 맞았습니다!

코드 구현

import sys
sys.setrecursionlimit(400000)

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]

def recursion(y, x): 
    if dp[y][x] != 0:
        return dp[y][x]
    
    for mv_y, mv_x in [[-1, 0], [1, 0], [0, -1], [0, 1]]: 
        dy, dx = y + mv_y, x + mv_x
        if 0 <= dy < N and 0 <= dx < N: 
            if graph[dy][dx] > graph[y][x]: 
                dp[y][x] = max(dp[y][x], recursion(dy, dx) + 1) 
    
    return dp[y][x]
    
for init_y in range(N):
    for init_x in range(N):
        recursion(init_y, init_x)
        
print(max(map(max, dp))+1) 

3. DP 접근(점화식)

점화식으로 접근하려 했지만, 논리적인 이슈가 발생했다. 현재 위치보다 더 큰 대나무 양을 가진 칸으로만 이동해야 하는 조건 때문에, DP 테이블이 올바르게 업데이트되지 않았다.

예를 들어, 특정 줄에 4 3 2 1로 대나무의 양이 분포되어 있다고 가정해보자.

• 올바른 DP 테이블 값은 [3, 2, 1, 0]이 되어야 하지만, 시도한 코드에서는 $(0,0) → (N-1,N-1)$으로 점화식을 전개하다 보니 모든 값이 [1, 1, 1, 1]로 업데이트되는 문제가 발생했다.

이 문제를 해결하기 위해 고민하던 중, 어차피 각 좌표를 한 번씩만 방문하며 주변을 확인하는 방식이라면, 대나무 양을 기준으로 정렬한 후 그 순서대로 좌표를 확인하면 되지 않을까? 라는 생각을 해봤다. 이를 바탕으로 코드를 추가했으며, 결과는 맞았습니다!

시도한 코드

#시도한 코드
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]

for y in range(N):
    for x in range(N):
        for mv_y, mv_x in [[-1, 0], [1, 0], [0, -1], [0, 1]]: 
            dy, dx = y + mv_y, x + mv_x
            if 0 <= dy < N and 0 <= dx < N: 
                if graph[dy][dx] > graph[y][x]: 
                    dp[dy][dx] = max(dp[y][x] + 1, dp[dy][dx])
                    
print(dp)

코드 구현

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]
#조건을 바탕으로 전개하기 위해(무조건 큰 값으로 이동해야 하니)
for_BUDP = [[graph[y][x], y, x] for x in range(N) for y in range(N)]
for_BUDP.sort(key= lambda x: x[0])

for daenamoo, y, x in for_BUDP: #daenamoo는 정렬을 위해 세팅했기에 사용 x
        for mv_y, mv_x in [[-1, 0], [1, 0], [0, -1], [0, 1]]: 
            dy, dx = y + mv_y, x + mv_x
            if 0 <= dy < N and 0 <= dx < N: 
                if graph[dy][dx] > graph[y][x]: 
                    dp[dy][dx] = max(dp[y][x] + 1, dp[dy][dx])

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

회고

점화식 접근에서 조건을 해결하기 위해 시간을 많이 보낸 것 같다. 그래도 이렇게 여러 가지 방법으로 문제를 풀어보면서 힘들지만 많은 생각도 할 수 있고, 나쁘지 않은 경험인 것 같다.. 앞으로도 꾸준히 이런 연습을 해봐야겠다.