[백준 1915 / Python] 가장 큰 정사각형

🧑🏻‍💻 문제링크

문제풀이

백준의 2차원 배열의 합 을 구하는DP의 개념을 알면 풀 수 있는 문제이다. 이 문제에서는 다음과 같은 점화식을 사용했다.

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

그림과 같이 2차원 배열이 주어졌을 때 동그라미로 표시된 부분에서

이렇게 빨간색 박스로 채운 정사각형이 1로만 되어있는 정사각형인지 확인을 하기 위해서는 위, 옆, 대각선이 0이 있는지 확인을 해야 한다. 그렇기 때문에 위의 점화식에서 해당 값은 (0 + 1)이 되므로 1이 될 것이다.(즉, 의미가 x)

그러면 1로 둘러싸인 부분을 확인을 보면 min값이 1, 여기서 1을 더하니깐 2가 된다. 그리고 2의 제곱을 해주면 4가 나오는 것을 확인할 수 있다.

DP를 설명할 때가 가장 어려운 것 같다. 뭐랄까 어떻게 되는지는 아는데 말로 표현을 못하겠다..? 아직 한참 멀은 것 같다. DP를 모르는 사람에게도 이해가 될 수 있도록 좀 더 연습해야겠다.

코드

n, m = map(int, input().split())
arr = [[0] * (m+1) for _ in range(n+1)]

# dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
dp = [[0] * (m+1) for _ in range(n+1)]

# 리스트 입력
for i in range(n):
    for idx, j in enumerate(list(map(int, list(input())))):
        arr[i+1][idx+1] = j

answer = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        # 배열의 값이 0이 아닌 경우
        if arr[i][j]:
            # 2차원 정사각형의 dp를 구해서 주변이 전부 1이면 2가 됨
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
            answer = max(dp[i][j], answer)

# 넓이를 구함
print(answer ** 2)

결과