[백준] 1937 욕심쟁이 판다

---

주어진 대나무 숲에서 가장 오래 살 수 있는 기간을 구하는 문제이다.

 

n*n 크기의 대나무 숲이 주어지고, 대나무가 더 많은 방향으로만 이동이 가능하다. 한 Cell당 하루를 살 수 있고 최대한 살 수 있는 기간을 구하기 때문에 DFS를 사용해야 한다는 것을 알 수 있다.

 

그리고 매 지점마다의 최대 값을 구하는 것 보다 이미 지나간 지점의 값을 저장해 놓는 것이 효율적이기 때문에  DP를 활용한다.

 

소스 코드

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

N = int(readline())
dp = [[0] * N for _ in range(N)]
_map = [[0] * N for _ in range(N)]
for i in range(N):
    line = [*map(int, readline().split())]
    for j in range(len(line)):
        _map[i][j] = line[j]

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

def dfs(y, x):
    for d in dp:
        print(d)
    print()
    if dp[y][x]:
        return dp[y][x]

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

        if 0<=nx<N and 0<=ny<N:
            if _map[ny][nx] > _map[y][x]: 
                dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1)

    return dp[y][x]


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

print(result)

 

 

혼자서 푸는 문제의 수가 줄어들고 있다. 일단 생각대로 구현을 해보고 안되면 다른 해결책을 찾자.

필요한 부분에 주석을 다는 습관을 가지자.