Category
알고리즘  DFS/BFS

[1937] 욕심쟁이 판다

by Hwang

문제

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

풀이

각각의 좌표들을 종착지라고 가정하고 dfs로 이 좌표가 종착지 였을 때의 이동 수들의 최대 값을 구하였고, 이렇게 구한 각각의 최대 이동수에서 가장 큰 값을 출력했다.

단순히 이렇게만 구현하면 시간초과로 인해 실패할 수 있는데 이를 해결하기 위해선 중복된 재귀 호출을 제거해주면 해결된다.

위의 테스트케이스로 예를들면 대나수의 개수가 11에 해당되는 arr[1, 1]까지의 최대 이동 수는 3일 것이다. (11→5→4), 이제 대나무의 개수가 15에 해당되는 arr[2, 1] 까지의 최대 이동 수를 구할 차례가 된다면 대나무 수가 11인 arr[1][1]를 거치게될 것인데, 이 과정에서 이미 구한 arr[1][1] 까지의 최대 이동 수를 이용하면 중복된 재귀를 제거할 수 있게 될 것이다.

import sys
sys.setrecursionlimit(10000)
moves = [(-1, 0), (1, 0), (0, 1), (0, -1)]
visited = dict()

def dfs(arr, x, y):
    if (x, y) in visited:
        return visited[(x, y)]
    m = 1
    for move_x, move_y in moves:
        new_x, new_y = x + move_x, y + move_y
        if new_x < 0 or new_x >= len(arr) or new_y < 0 or new_y >= len(arr):
            continue
        if arr[new_x][new_y] < arr[x][y]:
            m = max(dfs(arr, new_x, new_y) + 1, m)

    if (x, y) not in visited:
        visited[(x, y)] = m
    return m

n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]
max_move = -1
for i in range(n):
    for j in range(n):
        max_move = max(max_move, dfs(arr, i, j))
print(max_move)



 Comment