[백준, 파이썬] 1937번 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

이번 문제는 구현을 생각하는데 있어서 까다로웠던 문제였습니다. 

일단 그래프를 탐색하는데 있어서 dfs를 재귀적으로 구현, 또 탐색에 조건문을 달고, dp의 메모이제이션을 이용하여 연산 케이스 감소 등 3개의 콤비네이션을 이용한 구현이 필요했는데요.. 처음 구상한 주도 코드는 다음과 같습니다

어차피 조건에 항상 더 큰 숫자가 있는곳으로만 이동한다 하였으니, 다시 같은곳으로 되돌아오게될 경우를 

체크할 필요는 없습니다. 다만 문제에 주어진 조건을 잘 정의하고, 해당하지 않는경우는 pass, 

그리고 dfs로 탐색하게 될경우 재귀적으로 반환값을 받아 차례대로 각 이동경로마다의 best값을 설정하게 해주는 부분이 생각하기 까다로웠던것 같습니다.  

 

위 주도코드를 기반으로 작성한 코드는 다음과 같습니다. 

 

 

import sys n = int(input()) forest = [list(map(int, input().split(' '))) for _ in range(n)] dp = [[-1 for _ in range(n)] for _ in range(n)] direct = [(0,1),(0,-1), (1,0), (-1,0)] sys.setrecursionlimit(1000000) #중요, 선언하지 않으면 런타임 에러.. def dfs(i,j): if dp[i][j] != -1: return dp[i][j] else: dp[i][j] = 1 for k in direct: mv = tuple(sum(elem) for elem in zip((i,j), k)) if mv[0] <0 or mv[0]>=n or mv[1] <0 or mv[1]>=n or forest[i][j] >= forest[mv[0]][mv[1]]: continue else: dp[i][j] = max(dp[i][j], dfs(mv[0],mv[1])+1 ) return dp[i][j] def solve(): best = 0 for i in range(n): for j in range(n): best = max(best, dfs(i,j)) print(best) solve()

여기에서 중요한 부분은 sys.setrecursionlimit(1000000) 를 선언해주는 것이었는데요..

파이썬에서는 재귀적 탐색할 경우 탐색할 수 있는 깊이가 제한되어있어서 이렇게 리미트를 해제해야 합니다 

또한 dp[i][j]가 기본적으로 어떠한 값이 설정되어있다면, 그 값을 return하게 하여 불필요한 탐색경우를 줄였습니다. 

이상으로 욕심쟁이 판다 포스트를 마치겠습니다.