[백준][python]1937 욕심쟁이 판다

문제

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

소스코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) #백준 채점시 없으면 RecursionError 발생

if __name__ == "__main__":
        n = int(input())
        panda = [list(map(int,input().split())) for _ in range(n)]
        dp = [[1] * n for _ in range(n)]
        res = 0

        dx = [1,-1,0,0]
        dy = [0,0,1,-1]

        def dfs(x,y):
            if dp[x][y] > 1 : return dp[x][y] #이미 방문한 지점이면 dp 값 리턴
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if 0<=xx<n and 0<=yy<n and panda[xx][yy] > panda[x][y]: #현재 칸보다 대나무가 많으면 탐색
                    dp[x][y] = max(dp[x][y],dfs(xx,yy)+1)
            return dp[x][y]

        for i in range(n):
            for j in range(n):
                res = max(dfs(i,j),res)

        print(res)

설명

DFS를 이용해서 상하좌우를 탐색해준다 그리고 Top-down으로 DP를 사용해서 갈 수 있는 최대 거리를 메모이제션해 구한다.

 

1. 기존 dp 배열을 모두 1로 초기화한다. (하나는 나 자신 무조건있음)
2. 이차원 배열 순차적으로 최대 거리를 탐색한다.
3. dp를 사용해서 만약 방문한 이력이 있으면 (1이상이면) 그냥 패스한다. 한번이라도 지점을 지나면 DFS로 탐색이 완료되기 때문이다.
4. 방문한적 없으면 DFS로 탐색을 해준다. 이때 새로운 지점(xx,yy)에 대한 값을 정하는 것이 아닌 아래로 파고들면서 (Top-Down)으로 현재 지점의 누적 값을 구해준다. 
5. 3~4를 반복해서 모든 지점에 대한 최대 거리를 구한다.

후기

처음에 queue를 사용해서 bfs로 상하좌우를 탐색했다. bottom-up방식으로 누적을 해서 시간초과가 발생했다. 기존에 방문했던 곳을 피하는 것이 어려웠다.