[백준] 14925번: 목장 건설하기 Python - DP

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

14925번: 목장 건설하기

아 어렵다 원래 dfs밖에 기억이 안났는데 문제유형보고 DP란것을 알았다 

dfs로 풀면 대각선&상하좌우 8방향을 모두 확인해야하니까 시간초과가 날것 같다 

0의 개수를 dp 테이블에 누적하여 저장한다. 단 !! 1 또는 2를 만났을 때는 누적하면 안된다. 이걸 방지하기 위해서 

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1

대각선방향, 위쪽방향, 아래쪽 방향 중에 min 값을 선택한 후 , 자기자신을 카운트하기위해 1을 더하는 점화식이 나왔다. 

# 목장 건설하기
import sys
input = sys.stdin.readline
m, n = map(int, input().split())
array = []
dp = [[0]*(n+1) for _ in range(m+1)]
# array[0][0] 에 해당하는 dp 공간이 필요함
answer = 0
for i in range(m):
    array.append(list(map(int, input().split())))

for i in range(1, m+1):
    for j in range(1, n+1):
        if array[i-1][j-1] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
            # min 인 이유는 array[i-1][j-1] 가 1또는 2일때 dp[i][j]는 값 0에서부터 시작해야하기 때문이다. 
            answer = max(dp[i][j], answer)

print(answer)