[BOJ] 1937 - 욕심쟁이 판다 (Python)

 

 

아이디어

 

DFS로 각 지역에서 이동할 수 있는 최대 경로 길이를 저장해 나간 후, 숲에서의 최대 경로 길이를 구한다.

 

 

풀이

 

함수를 이용한 DFS를 위해 sys.setrecursionlimit으로 최대 재귀 깊이를 최대 대나무 숲의 크기인 500*500로 설정한다.

 

상하좌우로 이동하는 행열 변화 값을 리스트 delta에 저장하고, 숲의 크기를 n, 숲 정보를 2차원 리스트 forest에 저장한다.

방문 표시 및 최대 경로 길이를 저장하는 2차원 리스트 visited와 결과값을 저장하는 res를 만든다.

 

이중 for문을 돌며 각 칸에 대해 함수 dfs를 호출하는데, 해당 칸을 방문한 적이 있으면 함수를 바로 종료한다.

방문한 적이 없으면 해당 칸 방문 표시 이후, 현재 칸보다 대나무가 더 많은 근처 칸에 대해 dfs를 재귀 호출한다.

재귀 호출이 종료되면 현재 칸의 visited에 최대 경로 길이를 저장하고, res에 전체 최대 경로 길이를 저장한다.

 

 

import sys

sys.setrecursionlimit(250000)
input = sys.stdin.readline

delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(i, j):
    global res
    if visited[i][j]:
        return
    visited[i][j] = 1
    for di, dj in delta:
        if n > i+di >= 0 and n > j+dj >= 0:
            if forest[i+di][j+dj] > forest[i][j]:
                dfs(i+di, j+dj)
                visited[i][j] = max(visited[i][j], visited[i+di][j+dj]+1)
    res = max(res, visited[i][j])

n = int(input())
forest = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]
res = 0
for i in range(n):
    for j in range(n):
        dfs(i, j)
print(res)

 

 

대나무 숲에서 최대 250,000칸을 이동할 수 있다고 하더라도 재귀 깊이는 250,000까지 가지 않는다.

글을 작성하는 현재 시점의 테스트 케이스에서는 최대 재귀 깊이를 2,500으로 설정한 코드도 통과할 수 있다.

import sys

sys.setrecursionlimit(2500)

 

유효 인덱스 판단을 아래 코드처럼 하면 더 빠르긴 하나 비슷한 코드가 반복되어 가독성이 떨어진다고 느꼈다.

# 더 빠른 코드
def dfs(i, j):
    global res
    if visited[i][j]:
        return
    visited[i][j] = 1
    if i-1 >= 0 and forest[i-1][j] > forest[i][j]:
        dfs(i-1, j)
        visited[i][j] = max(visited[i][j], visited[i-1][j]+1)
    if i+1 < n and forest[i+1][j] > forest[i][j]:
        dfs(i+1, j)
        visited[i][j] = max(visited[i][j], visited[i+1][j]+1)
    if j-1 >= 0 and forest[i][j-1] > forest[i][j]:
        dfs(i, j-1)
        visited[i][j] = max(visited[i][j], visited[i][j-1]+1)
    if j+1 < n and forest[i][j+1] > forest[i][j]:
        dfs(i, j+1)
        visited[i][j] = max(visited[i][j], visited[i][j+1]+1)
    res = max(res, visited[i][j])