[BOJ] 가장 큰 정사각형

Jaden Kim·2022년 3월 18일
0

사용한 자료구조/알고리즘

주어진 배열에서 가장 큰 정사각형을 찾는 문제이다.
(0, 0) 지점에서 (n-1, m-1) 지점까지 순회하면서 dp를 활용하여 답을 찾았다.

각각의 칸 (r, c)에서는 자신을 둘러싸고 왼쪽+위쪽으로 2x2의 정사각형이 형성되는지 확인이 가능하다.
: (r, c), (r-1, c), (r, c-1), (r-1, c-1) 확인
dp[r][c]에는 어느 크기의 정사각형을 왼쪽+위쪽으로 이루고 있는지 저장한다.

이때 min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) 을 구하면,
2x2내의 왼쪽+위쪽의 칸들이 최소로 이루고 있는 정사각형의 크기를 구할 수 있다.

dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1

따라서 각각의 칸에 대해서 위의 코드를 적용시키면
정사각형의 크기를 누적해가면서 최대의 정사각형 크기를 구할 수 있다.

코드

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append([int(x) for x in list(input().strip())])
dp = [[0]*(m+1) for _ in range(n+1)]

for r in range(1, n+1):
    for c in range(1, m+1):
        if board[r-1][c-1] == 1:
            dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1

max_width = max([max(row) for row in dp])
print(max_width**2)

0개의 댓글