[백준 1937] 욕심쟁이 판다

문제

---

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

1937번: 욕심쟁이 판다

 

 

나의 풀이

---

DFS와 DP가 합쳐진 유형의 문제이다. 시작지점이 정해진 것이 아니므로 각 지점을 시작지점으로 했을 때 최장거리를 계산해 이들 중 다시 가장 큰 값을 답으로 출력하는 문제이다. 그냥 단순히 모든 지점을 시작점으로 해서 DFS로 탐색해도 되지만 이미 했던 연산을 중복해서 계산하므로 시간초과가 난다. 따라서 DP를 사용해 해당 지점을 시작점으로 했을 때 갈 수 있는 최장경로를 매 순간 기록해 메모이제이션을 한다.

 

코드

---

import sys
sys.setrecursionlimit(10**9)

def dfs(x,y):
    if dp[x][y]:
        return dp[x][y]
    dp[x][y] = 1
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    for dx,dy in dirs:
        nx, ny = x+dx, y+dy
        if 0<=nx<N and 0<=ny<N and forest[x][y]<forest[nx][ny]:
            dp[x][y] = max(dp[x][y], dfs(nx,ny)+1)
    return dp[x][y]

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