백준 - 가장 큰 정사각형 (1915)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (input[0], input[1])
var dp = [[Int]]()
var answer = 0

for i in 0..<n {
    let input = readLine()!.map { Int(String($0))! }
    dp.append(input)
    
    for j in 0..<m {
        if i > 0 && j > 0 && dp[i][j] == 1 {
            dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1
        }
        answer = max(answer, dp[i][j])
    }
}

print(answer * answer)

dp 테이블의 값은 dp[i][j]가 오른쪽 아래 꼭짓점일 때 그릴 수 있는 가장 큰 정사각형의 변의 길이 이다.

각 자리마다 배열의 값이 1이라면 대각선 왼쪽 위, 왼쪽, 위의 값을 비교해서 최솟값 + 1을 저장한다.