[Python/파이썬] 백준 1937 - 욕심쟁이 판다

문제 설명

 

입출력 예제

---

풀이 코드

어느 지점에서 출발해야 최대한 많은 칸을 지날 수 있는지를 찾아야 하기 때문에

각 지점별로 dfs로 재귀적으로 탐색하며 해당 위치에서 얼만큼 이동할 수 있는가를 dp에 저장한다.

답은 최대한 많은 칸을 이동해야하므로 가장 많은 칸을 이동할 수 있는 칸수를 dp에 저장된 값을 통해 반환한다.

 

정답 코드

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

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

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

def dfs(x, y):
    if dp[x][y] != 0: # 이미 한번 지난 경로일 경우 해당 지점의 dp값부터 시작
        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 and forest[nx][ny] > forest[x][y]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1) # 재귀가 끝나는 지점으로 이동할 수 있는 칸 개수 초기화
    return dp[x][y]

cnt = 0
dp = [[0] * n for _ in range(n)] # 해당 위치에서 이동할 수 있는 칸의 개수를 저장

for x in range(n):
    for y in range(n):
        if dp[x][y] == 0:
             cnt = max(cnt, dfs(x, y))

print(cnt)