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

접근

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

1937번: 욕심쟁이 판다

가장 먼저 단순한 bfs, dfs 문제로 접근했더니 시간 초과로 문제를 해결할 수 없었다. 문제를 해결하기 위해서는 중복 계산을 제거하는 방법을 고안해야 하는데, 중복을 제거하는 방법에는 두 가지 정도로 접근할 수 있었다.

1. 판다는 점점 더 높은 숫자를 향해서만 이동하기 때문에, 대나무의 양이 가장 작은 대나무의 위치부터 계산하여 점점 양이 많은 위치 순서로 탐색한다. 이렇게 탐색할 경우, 나중에 계산하는 위치가 무조건 앞에 계산했던 위치의 대나무 양보다 크기 때문에 해당 위치에서 상하좌우의 dp 값을 비교하여 가장 큰 값 + 1 로 입력하면서 계산해나가면 가장 큰 값을 구함으로써 답을 얻을 수 있다.
2. dfs 를 진행하면서 각 위치에서 가장 긴 경로를 메모이제이션 하면서 탐색을 진행하면, 나중에 다시 해당칸에 dfs 탐색 중에 도달하더라도 저장된 값을 리턴함으로써 중복 계산을 피할 수 있다.

이번 문제에서는 2번 방안이 더 빠른 문제 해결을 보여주었다.

코드

1번 코드

import sys
from collections import defaultdict

input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

N = int(input())
arr = defaultdict(list)
forest = [[0] * (N + 2) for _ in range(N + 2)]
dp = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(1, N + 1):
    tmp = [0] + list(map(int, input().split()))
    for j in range(1, N + 1):
        forest[i][j] = tmp[j]
        arr[tmp[j]].append((i, j))
        dp[i][j] = 1
maxVal = 1

for tree in sorted(arr.keys()):
    tmp_arr = arr[tree]
    while tmp_arr:
        r, c = tmp_arr.pop()
        for i in range(4):
            if forest[r + dr[i]][c + dc[i]] < forest[r][c]:
                dp[r][c] = max(dp[r + dr[i]][c + dc[i]] + 1, dp[r][c])
                maxVal = max(maxVal, dp[r][c])

print(maxVal)

2번 코드

import sys

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

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

N = int(input())
forest = [[0] * N for _ in range(N)]
dp = [[0] * N for _ in range(N)]
for i in range(0, N):
    tmp = list(map(int, input().split()))
    for j in range(0, N):
        forest[i][j] = tmp[j]
maxVal = 1


def dfs(r, c):
    global maxVal
    if dp[r][c] == 0:
        dp[r][c] = 1
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or N <= nr or nc < 0 or N <= nc:
                continue
            if forest[nr][nc] < forest[r][c]:
                dp[r][c] = max(dfs(nr, nc) + 1, dp[r][c])
    maxVal = max(maxVal, dp[r][c])
    return dp[r][c]


for i in range(N):
    for j in range(N):
        dfs(i, j)

print(maxVal)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!