[Algorithm] 가장 큰 정사각형 찾기

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12905

💬 Idea

• 처음에는 가장 긴 너비를 찾아서 2 이상일 경우 해당 영역의 모든 좌표가 1이라면 sqaure를 만들 수 있으므로 일일이 최고 너비를 찾아줬다. 그런데 이렇게 구현하니 효율성을 통과하지 못했다. 따라서 다른 풀이를 참고해서 풀었다!
• DP… ^~^ .. 신세계 발견..
  • 해당 인덱스의 map 값이 1일 경우 “왼쪽, 위쪽, 좌측 상단(↖️)의 최소값 +1 이 현재 길이가된다”는 원리를 이용해서 풀어주었다.

💬 풀이

import Foundation

func solution(_ board:[[Int]]) -> Int {
    var sqareCheckBoard = board
    var maxWidth = 0
    
    for i in 1..<board.count {
        for j in 1..<board[0].count {
            if board[i][j] == 1 {
                sqareCheckBoard[i][j] = min(sqareCheckBoard[i-1][j-1], sqareCheckBoard[i-1][j], sqareCheckBoard[i][j-1]) + 1
                if maxWidth < sqareCheckBoard[i][j] {
                    maxWidth = sqareCheckBoard[i][j]
                }
            }
        }
    }
    
    if board.count == 1 || board[0].count == 1 {
        for i in 0..<board.count {
            for j in 0..<board[0].count {
                if maxWidth < sqareCheckBoard[i][j] {
                    maxWidth = sqareCheckBoard[i][j]
                }
            }
        }
    }
    
    return maxWidth * maxWidth
}