[백준] 1937 욕심쟁이 판다 파이썬 후기

링크 : https://www.acmicpc.net/problem/1937

 

DP와 DFS를 적절히 섞어서 푸는 문제이다.

오래 매달리다가 해답을 검색해보고 풀었다.

 

 

푸는 방법

1. dfs에서 첫 방문하는 지점을 1로 초기화한다.

2. 주변 4방향에 더 큰 값이 있는지 비교해보고, 있으면 현재값과 비교해 더 큰 값을 취한 뒤, 더 방문할 곳이 없으면 반환한다.

3. 모든 지점에 대해 1,2를 반복한다.

 

오래 걸렸던 이유

1. 고정관념

백준에서 다이나믹 프로그래밍 카테고리에 있어 DP만으로 풀어보려고 했는데,

DP만으로 불가능하단 생각이 들고나서야 DFS를 생각하고 접근해보았다.

이 생각이 들기까지 시간이 오래 걸린 것도 나의 공부가 모자란 것도 컸다.

다음부턴 문제를 꼭 DP라고만 생각하지 않고 어떻게 풀지를 초점으로 두어야겠다.

 

2. 코딩 실수

DFS로 어느 지점을 방문하는 지는 알고 있었지만, DFS를 DP와 접목시키는 방법이 잘못됐었다.

DFS로 그냥 방문하는 지점이 생길 때마다 +1 해줘야 했는데 DP에 어떻게 접목시킬지 생각하다가 꼬여서 스스로 무덤을 팠다.

게다가 코딩 에러로도 배열의 인덱싱을 벗어나면 안되는 게 당연한건데 시간이 걸렸다.

 

3. DP 접근 방법 착오

2번과 엮인 이야기로 DFS에서 받은 결과값을 DP를 이용해 비교해야 하는데,

막연하게 DP를 써야된다는 느낌만 있었고, 정확하게 알지 못했다.
지금 보니 DFS로 최대 깊이는 받을 수 있었지만 비교하는 방법이 잘못 됐었다.

 

코드

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


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

def find_new_food(x, y):
    if dp[x][y]:
        return dp[x][y]
    dp[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if forest[x][y] < forest[nx][ny]:
                dp[x][y] = max(dp[x][y], find_new_food(nx, ny) + 1)
    return dp[x][y]

N = int(input())
forest = [0 for i in range(N)]
dp = [0 for i in range(N)]
for i in range(N):
    forest[i] = list(map(int, input().split()))
    dp[i] = [0 for i in range(N)]
max_value = 0
for i in range(N):
    for j in range(N):
        max_value = max(max_value, find_new_food(i, j))
print(max_value)