BOJ 14925 - 목장 건설하기

문제

백준 온라인 저지 - 14925번

풀이 과정

가장 큰 정사각형을 찾는 동적 계획법 문제입니다.

그냥 완전 탐색 으로 찾으려 할 경우 O(N^4) 이기 때문에 시간 초과가 발생하게 됩니다.
dp[x,y] = (x, y)지점을 왼쪽 모서리로 하는 가장 큰 정사각형의 한 변의 길이 라고 정의한다면
다음과 같은 점화식을 얻을 수 있습니다.

dp[x][y] = min(dp[x + 1][y], dp[x][y + 1], dp[x + 1][y + 1]) + 1

이때 격자를 벗어나는 위치나 장애물이 있는 경우를 기저 사례로 처리해줍니다.

코드

import sys

sys.setrecursionlimit(10**6)

M, N = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
memo = [[-1] * N for _ in range(M)]


def dp(x, y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return 0
    if board[x][y] != 0:
        return 0

    if memo[x][y] != -1:
        return memo[x][y]

    memo[x][y] = min(dp(x + 1, y), dp(x, y + 1), dp(x + 1, y + 1)) + 1

    return memo[x][y]


def solution():
    answer = 0

    for x in range(M):
        for y in range(N):
            L = dp(x, y)
            answer = max(answer, L)

    return answer


print(solution())