kingsubin

• 정사각형의 조건 검사하자는 걸로 접근: 정사각형 한 변의 길이가 짝수, 홀수로 구분하여 정사각형의 중심을 기준으로 생각, 가능하려면 적어도 인접한 두 지점이 1이어야 함.
• 중간까지 시도 하다가 너무 복잡해지고 접근을 잘못한 거 같단 생각 들고 못 품.
• 다른 답변 보고 제출했는데 나중에 비슷한 문제 똑같이 풀 수 있을지 모르겠음..

 

• 변의 길이가 1 보다 큰 정사각형 안에는 그보다 작은 정사각형이 있음.
• dp 생각, 점화식 세우기
• dp(i, j) = i, j 를 우하단으로 하는 정사각형의 최대 변 길이
• dp(i, j) = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

n, m = map(int, input().split())
board = [input() for _ in range(n)]
dp = [[0] * m for _ in range(n)]

for j in range(m):
    if board[0][j] == '1':
        dp[0][j] = 1

for i in range(1, n):
    if board[i][0] == '1':
        dp[i][0] = 1

    for j in range(1, m):
        if board[i][j] == '1':
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))

print(ans ** 2)

 

 

---

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