백준 1937번: 욕심쟁이 판다

BOJ

백준 1937번: 욕심쟁이 판다

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

접근

n × n의 크기
상, 하, 좌, 우 중 한 곳으로 이동
그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다
최대한 많은 칸을 방문

처음에 DFS만 이용해서 풀었는데, 틀렸다. 검색해보니 DFS와 DP를 함께 사용하는 해답이 있어서, 그 방법을 이용했다. 최대한 많은 칸을 방문하는 문제이기 때문에 탐색을 이용하는 거라 생각했다. 구체적으로 왜 DFS를 이용해야 하는지는 아직 잘 모르겠다. 왜 DP를 함께 사용하는지도 잘 모르겠다. 충분한 이해가 필요한 거 같다.

예제 입력

n=4	[0]	[1]	[2]	[3]
[0]	14	9	12	10
[1]	1	11	5	4
[2]	7	15	2	13
[3]	6	3	16	8

DP 배열

n=4	[0]	[1]	[2]	[3]
[0]	1	3	1	2
[1]	3	2	3	4
[2]	2	1	4	1
[3]	3	4	1	2

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

dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1)
위의 문장이 처음에는 이해가 되지 않았다. dp[y][x]가 아닌 dp[ny][nx]에 새로운 값을 업데이트 해줘야 한다고 생각했었다. 왜 그렇게 생각했는지 모르겠지만, 방향성을 잘못 잡은 거 같다. dp[i][j] = [i][j]칸에서 이동할 수 있는 칸의 최대값으로 생각하면 이해하기 쉬울 거 같다.

Correct Solution

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

def dfs(y, x):
    if dp[y][x]: return dp[y][x]

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

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

    return dp[y][x]

N = int(input())
forest = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]

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

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

print(answer)

참고 사이트

깨지고 부서져라