1️⃣ 서론
백준 문제 1937번 욕심쟁이 판다 문제이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
n * n 크기의 대나무 숲이 있고 판다는 상, 하, 좌, 우로 이동이 가능하다.
하지만 판다는 욕심이 많아 다음 이동할 지역이 대나무가 많아야 한다는 조건이 있다. 안그러면 죽는다고 한다.
판다가 살 수 있는 최대 일수를 구하는 것이 문제이다.
3️⃣ 풀이
상, 하, 좌, 우로 이동해서 최대 일수를 구한다는 것에서 dfs를 바로 떠올릴 수 있었다. 하지만 최대 500 * 500 칸이여서 모든 칸을 검사하면 시간초과가 걸릴거 같아 걱정되어 시간을 줄이기 위해 어떻게 해야할지 고민하였다.
dfs로 하는 것은 확정되었고 경로를 반복해서 이동하는 문제를 줄이기 위해 dp를 사용하였다. dp를 사용하자는 아이디어를 생각해내는 것이 이 문제의 키포인트가 아니었나 싶다. 코드를 살펴보도록하자
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def dfs(x, y):
if dp[x][y]: 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 arr[x][y] < arr[nx][ny]:
dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)
return dp[x][y]
n = int(input())
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
dp = [[0] * n for _ in range(n)]
answer = 0
for i in range(n):
for j in range(n):
answer = max(answer, dfs(i, j))
print(answer)
5️⃣ 마치며
dp 와 dfs를 같이 사용한다는 점에서 쉽지만은 않았던 문제였던 것 같다. 아직 두개의 개념을 같이 사용하는데 익숙하지는 않아서 많은 훈련이 필요할 것 같다.
