[Python/파이썬] 백준 14925번 목장 건설하기

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

 

풀이

점화식: `dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`

1. dp[i][j]는 현재 위치(빨간색).
2. 왼쪽(노란색), 위쪽(파란색), 대각선 왼쪽 위(검은색) 방향의 dp 값들을 확인한다.
3. 이 세 값 중 최솟값에 1을 더한다.

그림에서 'a'로 표시된 부분들은 기존에 만들어진 정사각형의 변을 나타내고, '1'로 표시된 부분은 새로 추가되는 1칸을 의미한다.

이렇게 세 방향의 최솟값을 사용하는 이유는 정사각형이 되려면 세 방향 모두가 정사각형의 일부가 되어야 하기 때문이다. 만약 세 방향 중 하나라도 작은 값이 있다면, 그 방향으로는 더 큰 정사각형을 만들 수 없다. 따라서 가능한 최대 정사각형의 크기는 세 방향의 최솟값에 1을 더한 값이 된다.

코드

m, n = map(int, input().split())
map_data = [list(map(int, input().split())) for _ in range(m)]

dp = [[0]*(n+1) for _ in range(m+1)]
answer = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        if map_data[i-1][j-1] == 0:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
            if dp[i][j] > answer:
                answer = dp[i][j]
print(answer)