백준(Baekjoon) 1937번 : 욕심쟁이 판다 - python 풀이

🔴 문제 개요

문제 원문 - 백준 온라인 저지(Baekjoon Online Judge)

🚀 난이도 : GOLD 3

판다가 $N \times N$ matrix의 임의의 지점에서 출발해 상, 하, 좌, 우 대나무가 더 많은 방향으로 움직일 수 있을 때, 최대 이동할 수 있는 칸 수를 구하면 되는 문제

제한 사항

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

🟠 Solution

🚩 시행 착오 (DFS, BFS)

단순 그래프 탐색 문제라고 생각할 수 있는 문제에서는 늘 조심해야 합니다. 모든 칸에서 출발하는 DFS나 BFS를 실행한다고 가정할 때, 한 번의 그래프 탐색 시간 복잡도가 O(N^2) 라고만 생각해도 500 x (500 x 500) 이상의 연산이 수행되게 됩니다. 이러한 방법은 N이 10의자리 수로 주어질 때 가능한 풀이라고 생각하면 좋을 것 같습니다.

🏁 DFS + DP

그렇다면 이러한 상황에서는 탐색을 수행하는 횟수를 줄여야 합니다. 이미 탐색된 케이스에 대한 횟수는 저장해놨다가 활용하는 메모이제이션, 즉 DP 방법론을 활용할 수 있습니다.

이를 위해서는 특정 좌표에 도달하기 이전의 경로와 이후의 경로가 중복되면 안됩니다. 이러한 모순이 생긴다면 메모이제이션으로 저장된 횟수가 올바르지 않은 것입니다. 이번 문제에서는 대나무가 더 많은 칸으로 이동할 수 있다는 문제의 조건이 이를 보장해줍니다.

이 조건 때문에 특정 칸에 도달하는 경우는

1. 처음 해당 칸부터 출발하는 경우
2. 대나무가 더 적은 칸에서 해당 칸으로 이동한 경우

위 두 가지 경우 밖에 존재할 수 없습니다. 즉, 특정 칸 이후의 도달할 경우에 대해서 생각할 때 해당 칸 이전의 경로와 절대로 중복될 수 없습니다. 이전 칸은 없거나, 대나무가 더 적은 칸이기 때문입니다. 따라서 특정 칸부터 시작해 탐색하는 경우의 수를 독립적으로 메모이제이션할 수 있습니다.

import sys
from typing import Tuple

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

def dfs(points: Tuple[int]) -> int:
	"""
    points 좌표부터 시작해 대나무가 더 많은 방향으로 갈 수 있는 칸을 반환한다.
    탐색 도중 다른 시작 좌표에서의 탐색 중복을 고려해 memoization을 진행한다.
    """
    y, x = points

	# 이미 탐색이 진행된 좌표의 경우 그대로 값을 return
    if dp[y][x]:
        return dp[y][x]

	# 해당 좌표부터 시작하는 경우
    dp[y][x] = 1

    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        
        # 상, 하, 좌, 우 중 대나무가 더 많은 좌표로 탐색
        if 0 <= ny < N and 0 <= nx < N and matrix[y][x] < matrix[ny][nx]:
        	# memoization
            dp[y][x] = max(dp[y][x], dfs((ny, nx)) + 1)
	
    # momoization 이후 반환
    return dp[y][x]

# input
N = int(input().rstrip())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]

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

answer = 0

for r in range(N):
    for c in range(N):
        tmp = dfs((r, c))
        if answer < tmp:
            answer = tmp
# output
print(answer)

🤔 고찰

• 단순 그래프 탐색이라고 생각되는 문제라도 N의 범위를 생각해봐야 합니다. 특히 모든 좌표에서 그래프 탐색을 실행해야 하는 경우 조심해야 합니다.
  • N이 100의 자리라면 100x(100x100), 기본 천 만번 이상의 연산이므로, 1초에 2천 만번의 연산을 수행하는 파이썬의 속도를 고려해야 합니다.
• 이런 경우 DFS 과정에서 메모이제이션을 활용하는 DP 방법론을 적용할 수 있습니다.
  • 이 때, 특정 경로에 대한 메모이제이션의 경우 해당 좌표 도달 이전의 경로와 이후의 경로가 독립적인지를 판단해야 합니다. 위 문제의 경우 문제의 조건이 이를 보장해줍니다.

🙏 문제의 접근 방법 및 코드에 대한 피드백은 환영입니다!