[백준 1937] 욕심쟁이 판다 (Python)

문제 : 

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

1937번: 욕심쟁이 판다

 

1. 문제 이해하기

• 그래프 크기 n * n (1 <= n <= 500)의 대나무 숲이 있습니다. 각 칸에는 대나무의 개수가 적혀있습니다.
• 판다는 대나무를 그래프 상의 특정 칸에서 대나무를 먹고 상, 하, 좌, 우 중 한 곳의 칸으로 이동합니다. 이때, 자리를 옮길 때 현재 칸보다 대나무가 더 많은 칸으로만 이동합니다.
• 이때, 판다가 최대로 이동할 수 있는 칸의 개수의 최댓값을 출력합니다.

 

2. 문제 풀이 생각하기

1. 처음에는 단순 dp 또는 bfs를 생각했는데 dp는 상, 하, 좌, 우를 구현하기에 쉽지 않았고, bfs는 각 지점을 방문할 때마다 visited(방문 체크)를 계속 갱신해야 한다는 생각 때문에 dfs + dp로 풀이 방식을 바꿨습니다.
2. 중첩 for문으로 방문하지 않은 지점에서 dfs(깊이 우선 탐색) 시작
3. 이미 방문한 지점이면 해당 칸에서의 dp값 리턴
4. 처음 방문하는 칸은 현재 칸의 dp를 1로 갱신
5. 4방향 체크, 4방향 중 현재 칸보다 대나무 수가 많으면 해당 좌표로 깊이 우선 탐색을 합니다.
6. 가장 깊은 깊이에 들어갔을 때 주변에 해당 칸보다 큰 값이 없으면 해당 칸의 dp값 리턴
7. 리턴된 dp값 + 1과 현재의 dp값과 비교해서 큰 값으로 갱신
8. ans값도 갱신
9. 2 ~ 8 반복
10. ans값 출력

 

간단한 예시로 설명하겠습니다.

숲과 숲의 칸과 대응하는 dp입니다.

4에서 시작해서 5에 도달했을 때, 5를 기준으로 상, 하, 좌, 우에 5보다 큰 값이 없으므로 현재 위치의 dp값 1을 리턴합니다.

가장 깊이 있는 곳을 기준부터 거리를 증가시킵니다.

 

3. 차근차근 구현하기

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1 for _ in range(n)] for _ in range(n)]
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ans = 1

def boundary(i, j):
    return 0 <= i < n and 0 <= j < n

def dfs(i, j):
    global ans
    # 이미 방문했다면 해당 지점의 dp값부터 시작 -> 리턴
    if dp[i][j] != -1:
        return dp[i][j]
    dp[i][j] = 1 # 기본 방문 체크
    for k in d:
        ni = i + k[0]
        nj = j + k[1]
        if not boundary(ni, nj):
            continue
        if g[i][j] < g[ni][nj]:
            count = 1   
            count += dfs(ni, nj)
            dp[i][j] = max(dp[i][j], count) # dfs가 풀릴 때 풀리는 지점을 기준으로 거리 갱신
            ans = max(ans, dp[i][j]) # 가장 먼 거리 갱신
    return dp[i][j]

for i in range(n):
    for j in range(n):
        if dp[i][j] == -1:
            dfs(i, j)
print(ans)

 

4. 피드백

• 판다처럼 욕심을 부리지 말자.