백준_1937_욕심쟁이 판다

문제

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

1937번: 욕심쟁이 판다

풀이

1) DFS

원점을 옮겨가면서 깊이 우선 탐색을 진행한다. 단순하게 dfs만으로 구현하면, 시간초과를 만나게 된다.

시간을 줄이기 위해 DP를 이용해야 한다. 

2) DP

2차원 배열을 선언해 한번 방문한 노드는 다시 방문하지 않도록 처리하면, 시간을 줄일 수 있다.

3) 기타

매번 dfs를 while문을 쓰다보니, 재귀범위를 넓히는 것을 잘 잊어버린다. 자주 써봐서 익숙해지기!!

이런식의 문제를 코테에서 한번 봤었다. DP를 써야하는데, 어떻게 해야하는지 감을 못잡아서 그냥 DFS만으로 처리했었다. 이번 기회에 확실하게 알아두기!

코드

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

N = int(input().strip())
board = [list(map(int, input().strip().split())) for i in range(N)]

DIR = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dp = [[0]*N for i in range(N)]

def dfs(r, c) :
    if dp[r][c]>0 : return dp[r][c] # 이미 지난 경로를 체크
    dp[r][c] = 1
    
    for dr, dc in DIR : 
        nr, nc = dr+r, dc+c
        if 0<=nr<N and 0<=nc<N :
            if board[nr][nc]> board[r][c] : 
                dp[r][c] = max(dp[r][c], dfs(nr, nc)+1)
    
    return dp[r][c]

ans = 0
for r in range(N) : 
    for c in range(N) : 
        ans = max(ans, dfs(r, c))

print(ans)