[Python] 백준 / gold / 1937 : 욕심쟁이 판다

문제 링크 : https://www.acmicpc.net/problem/1937

DFS + DP 문제다. 전에 티스토리 블로그에 정리했던 내리막길 https://heyksw.tistory.com/8 이랑 비슷한 문젠데, 그때도 이런 유형을 어려워 했었는데 아직도 어렵다..

dfs 함수 내 코드를 작성할 때 먼저 (if dp 값 있는 경우, else dp 값 없는 경우) 이렇게 나누고 시작하는게 좋은 것 같다.

dp 문제를 풀때는 dp[x][y] 의 의미가 무엇인지 부터 확실히 정하고 시작해야겠다. 여기서 dp[x][y] 의 의미는 (x, y) 에서 먹으러 갈 수 있는 최대 대나무 수다.

3가지 얻어갈 것

1. visit 리스트를 생성할 필요가 없다. 어차피 계속 큰곳으로만 이동하기 때문에 전에 방문했던 곳을 다시 방문하게 될 경우가 아예 없다. 그리고 visit 리스트를 사용하면 오히려 고려못해주는 경로가 생기게 된다.
   이건 내리막길 문제를 풀 때도 헷갈렸던 부분.

2. dfs 함수 내부에서 저렇게 복잡하게 코드를 작성할 필요없이 if, else 로 dp 값이 있는 경우와 없는 경우. 크게 2개로 나눠서 짜는게 훨씬 좋다.

3. 처음에 go 라는 플래그 변수를 도입했는데, 이것도 필요가 없다. 현재 미방문 dp 일경우 (dp 값이 -1 인경우), 코드 초반부에 아예 dp 값을 1로 저장한 다음에 for 문을 돌리고, 더 이상 갈 수 있는 곳이 없다면 자동으로 dp 값이 1만 그대로 남기 때문이다.

처음에 작성한 오답 코드

import sys
n = int(sys.stdin.readline())
graph = []
dp = [[-1]*n for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


# 시작 좌표, 현재 좌표, 방문처리, 현재 먹은 대나무들
def dfs(a, b, x, y, visit, path):
    #print(x, y)
    visit[x][y] = True
    # 더 이상 먹으러 갈곳이 있는지
    go = False
    for d in direction:
        nx = x + d[0]
        ny = y + d[1]
        if 0 <= nx < n and 0 <= ny < n:
            if not visit[nx][ny] and graph[nx][ny] > graph[x][y]:
                go = True
                if dp[nx][ny] == -1:
                    dfs(a, b, nx, ny, visit, path+1)
                # 이미 dp 처리된 곳을 만나면
                else:
                    dp[a][b] = max(dp[a][b], path + dp[nx][ny])
                    #print(1, 'dp', a, b, '=', dp[a][b])

    # 더 이상 먹으러 갈곳이 없으면
    if not go:
        dp[a][b] = max(dp[a][b], path)
        #print(2, 'dp', a, b, '=', dp[a][b])
        return


for x in range(n):
    for y in range(n):
        visit = [[False] * n for _ in range(n)]
        #print('dfs',x,y,'start')
        dfs(x, y, x, y, visit, 1)
        #print()


answer = 0
for x in dp:
    answer = max(answer, max(x))

print(answer)

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
graph = []
dp = [[-1]*n for _ in range(n)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


def dfs(x, y):
    # 이미 처리했을 경우 dp 값 사용
    if dp[x][y] != -1:
        return dp[x][y]
    # 처리하지 않은 경우
    else:
        # 지금 먹은 곳 1.
        dp[x][y] = 1
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            if 0 <= nx < n and 0 <= ny < n and graph[x][y] < graph[nx][ny]:
                # for 문을 도는 동안 최댓값이 교체될 수 있기 때문에 max 함수 사용
                # 1 + dfs(nx, ny) 인 이유는 현재 먹은 곳 (1) + 다음 먹으러 갈 곳 (dfs) 이기 때문
                dp[x][y] = max(dp[x][y], 1 + dfs(nx, ny))
        # go = True, False 와 같은 플래그를 사용하지 않아도 된다.
        return dp[x][y]


for i in range(n):
    for j in range(n):
        dfs(i, j)
# sum 을 이용한 2차원 -> 1차원 배열 변경
print(max(sum(dp, [])))