[BOJ] 1937. 욕심쟁이 판다(Python) / DFS + DP

1937번: 욕심쟁이 판다

 처음 이 문제를 DFS 각 위치별 완전탐색으로 접근했더니 답은 금방 구했지만, 바로.. 시간초과가 떴다.. 아니나 다를까 DFS + DP의 콜라보로 풀어야 하는 문제였다. 즉, Memoization을 해야한다는 것!

Memoization은 이미 한 번 탐색한 위치에 대해서는 재귀로 더 탐색할 필요 없이 그냥 그 값을 가져다 사용할 수 있도록 해당 위치별 값을 미리 저장한 DP Table을 만들어두는 것이 포인트다! 즉, 불필요한 반복 연산 없이 한 번 탐색으로 끝내버린다!

사실 이게 말로는 쉬운데.. 구현해내기가 너무나 힘들었다.. 결국 다른 분의 코드를 보고 이해한 후 내 방식으로 변형해서 짠 코드이다. 세상에 진짜 머리 좋은 사람들 너무 많다.. 나도 빨리 잘 해야지

• 사용 알고리즘 : DFS + DP
• 우선 main 코드에서 DFS는 DP Table에서 첫 방문일 때만 dfs 함수를 실행시킨다.
• 가장 중요한 함수인 dfs함수를 보면,
  • 시작 부분에 이미 방문한 적이 있을 때를 표현한다. (아래에서 재귀로 호출되는 경우)
  • 만약 첫 방문이라면 해당 위치는 무조건 먹을 수 있으므로 check[r][c] = 1
  • 이후, 상하좌우 4방향에 대해 이동할 위치에 대나무가 더 많다면
    • 해당 위치는 (원래 해당 위치에 있던 값)과 (이동할 위치에 있던 값에 +1 한 값)의 최댓값으로 갱신한다.
    • 즉, 판다가 오래 사는 일수 = 4방향 중 판다가 가장 많이 이동한 횟수(최장 경로) + 1
  • 그리고 갱신된 현재 값 혹은 갱신되지 않은 현재 값을 리턴한다.
• 최종적으로 그려진 DP Table의 각 위치별 최장거리 값 중 최댓값을 출력한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def dfs(r, c):
    if check[r][c]:		# 방문한 적이 있다면 해당 값을 그대로 가져다 사용
        return check[r][c]

    check[r][c] = 1     	# 첫 방문 시 해당 위치는 무조건 먹을 수 있으므로 1
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if not (0 <= nr < N and 0 <= nc < N):
            continue
        
        if A[r][c] < A[nr][nc]:		# 이동할 곳에 대나무가 더 많다면
            # 판다가 오래 사는 일수 = 4방향 중 판다가 가장 많이 이동한 횟수(최장 경로) + 1
            check[r][c] = max(check[r][c], dfs(nr, nc)+1)
    return check[r][c]

# main
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
check = [[0] * N for _ in range(N)]     # DP Table(for memoization)

for r in range(N):
    for c in range(N):
        if not check[r][c]:		# 첫 방문이 아닌 경우에만 dfs 실행
            dfs(r, c)
MAX = 0
for i in range(N):
    MAX = max(MAX, max(check[i]))
print(MAX)

---

• 시간 : 324ms / 메모리 : 171872kb
• 고찰 : 헥.. 이 문제는 뭔가 예전에 www.acmicpc.net/problem/1520 내리막길 문제 풀었을 때와 비슷한 아이디어로 접근해야 했다. 어려웠다ㅜㅜ.. 완탐으로 안 될 때는 DFS + DP로 풀 수 있는지 확인하고 접근해보자. 내 설명보다 코드로 print() 찍어가며 이해하는 게 더 빠를 것 같다.. 코딩만이 살 길이다. Keep Going