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

🐳 링크

백준 1937번 욕심쟁이 판다

🐕 문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

🐾 풀이 방법

1. 먼저, 입력을 다 받고 난 뒤 check라는 이동값을 저장해줄 리스트를 선언한다. 이 check 에는 특정 [i][j] 칸까지의 이동 거리를 저장한다.
2. 상 하 좌 우, 더 큰 값으로 이동하며 이전 check값과 비교하여 update를 해준다.
   이 때, 단순히 +1을 하고 dfs를 계속 돌게 되면 시간 초과가 발생한다. 이 문제는 dp스럽게 풀어야하므로, 단순히 +1을 하는 것이 아닌 현재의 check 값과, 바뀐 인덱스로 dfs 돌고 난 이후의 check값 중 더 큰 값으로 업데이트 한다.
   이는 조금 다른 개념이기도 한데, dp로 풀기 위해서는 dfs를 탐색용이 아닌, 현재 위치의 check 값을 찾아간다고 생각할 수 있다.
3. check에 가장 알맞은 값이 저장된 뒤 더 이상 갈 인덱스가 없다면 해당 check 값을 리턴한다.
4. check 배열에 가장 큰 값을 print한다.

solution 코드

import sys
sys.setrecursionlimit(10 ** 5)
sys.stdin = open("input.txt","rt")

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

def dfs(x,y):
    if check[x][y]: #체크가 0이 아닌 경우 (이미 다녀온 경우)
        return check[x][y] #체크를 리턴해줌.
    check[x][y] = 1 # 체크가 0인 경우에는 체크를 1로 초기화해줌.
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위에 알맞은 nx,ny에 대하여 대나무개수도 더 많다면,
        if 0 <= nx < n and 0 <= ny < n and forest[x][y] < forest[nx][ny]:
            # 해당 체크에 기존의 체크와, dfs를 돌고 난 뒤의 체크값에 +1 한 값 중 더 큰 값을 저장
            # 1을 더하는 이유는 기존 값에서 더 나아간 경우이므로 한칸을 추가해주는 것과 같다.
            check[x][y] = max(check[x][y], dfs(nx,ny) + 1)
    return check[x][y]


n = int(sys.stdin.readline())
forest = []
for _ in range(n):
    forest.append(list(map(int,sys.stdin.readline().split())))

check = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        check[i][j] = dfs(i,j) # 체크 배열에, dfs를 통해 얻은 해당 체크의 값을 저장.
print(max(map(max,check)))

시간초과 코드

import sys
sys.setrecursionlimit(10 ** 5)
sys.stdin = open("input.txt","rt")

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

def dfs(x,y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and forest[x][y] < forest[nx][ny]:
            if check[nx][ny] == 1 or check[x][y] + 1 > check[nx][ny]:
                check[nx][ny] = check[x][y] + 1
                dfs(nx, ny)


n = int(sys.stdin.readline())
forest = []
for _ in range(n):
    forest.append(list(map(int,sys.stdin.readline().split())))

check = [[1] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if check[i][j] == 1:
            dfs(i,j)

res = 0
for i in range(n):
    comp = max(check[i])
    res = comp if res < comp else res

print(res)