[Python] 욕심쟁이 판다

욕심쟁이 판다

분석

• 대나무를 먹고 상,하,좌,우 중 한 곳으로 이동하여 또 먹음
• 자리를 옮기면 옮긴 지역에 전 지역보다 대나무가 많이 있어야 한다
• 어떤 지점에 처음 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 최대한 많은 칸을 방문할 수 있는지

입력

• N: 대나무 숲의 크기
• 대나무 숲의 정보

출력
판다가 이동할 수 있는 칸의 수 최댓값

틀린 풀이...

from collections import deque

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    visited = set()
    queue = deque()
    queue.append((x, y))
    visited.add((x, y))
    count = 0

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited:
                if A[nx][ny]-1 > A[x][y]:
                    A[x][y] -= 1
                    visited.add((nx, ny))
                    queue.append((nx, ny))
                    count += 1

                    A[nx][ny] -= 1

    return count

max_count = 0


for i in range(N):
    for j in range(N):
        max_count = max(max_count, bfs(i, j))

print(max_count)

• bfs 돌면서 현재 위치보다 숫자가 크면 이동시키는 방식으로 풀었다
• 다음 칸 숫자 하나 줄이면서 계속 돌렸는데 틀렸다!!
  (근데 지금 보니 그냥 이 로직 자체를 구현한 것도 틀린 듯)

다른 블로그를 찾아보다가
dp + dfs로 풀어야 한다는 걸 알았다...

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1] * N for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

answer = 0

def dfs(x,y):
    if dp[x][y] == -1:
        dp[x][y] = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and A[nx][ny] > A[x][y]:
                dp[x][y] = max(dp[x][y], dfs(nx,ny))

    return dp[x][y] + 1

for i in range(N):
    for j in range(N):
        answer = max(answer, dfs(i,j))

print(answer)

• sys.setrecursionlimit(10**6) 없이 처음 제출했을 때는 런타임에러가 났다...
• 잘 기억해야 할듯....