[Python/파이썬] 백준 1937번 욕심쟁이 판다

 

1937번: 욕심쟁이 판다

 

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
visited = [[0]*n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


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


ans = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            dfs(i, j)
for i in range(n):
    for j in range(n):
        ans = max(ans, visited[i][j])
print(ans)

대나무 숲과 크기가 똑같은 2차원 배열 visited를 만들어서 해당 칸에서 출발하여 조건에 맞게 이동했을때 갈 수 있는 경로의 길이의 최대값을 저장한다. 

dfs 함수는 실행될 때마다 상하좌우로 인접한 4칸에 대해 둘러보며 이동할 수 있는 칸인지 알아본다. 이동할 수 있는 칸인데 아직 방문하지 않은 경우 visited 값이 0일 것이므로 이 경우에는 그 칸에 대해 dfs를 재귀적으로 수행해서 경로를 더 탐색하여 visited[nx][ny]의 값을 채운다. 이미 방문했던 칸이라면 그 칸 (nx, ny)에서 출발하여 갈 수 있는 최대값이 visited[nx][ny]에 이미 저장되어 있을 것이다. dfs를 하여 경로를 더 탐색하든 이미 저장된 값을 사용하든 (visited[nx][ny]에 저장된 값+1)과 visited[x][y]의 값을 비교하여 더 큰 값을 visited[x][y]에 저장해준다. dfs의 인자로 받은 값에 해당하는 칸이 더이상 이동할 곳이 없는 칸이라면 visited[x][y]의 값은 1인채로 함수가 종료될 것이다.