배열에서 가장 큰 정사각형 찾기

프로그래머스에서 제공하는 문제 중에 하나라고 합니다.

 

배열 내부를 탐색하여 가장 큰 정사각형을 찾는 알고리즘입니다.

 

1로 만들수 있는 가장 큰 정사각형을 만들면 됩니다.

 

성능상의 문제가 있기 때문에 성능을 고려하여 DP(Dynamic Programming)를 사용하여 구현할 수 있습니다.

저는 swift 쟁이라서 이걸로 짰습니다.

func solution(_ board:[[Int]]) -> Int {
    var copy = board
    
    var answer = 0
    let yCount = copy.count
    let xCount = copy[0].count
    var max = 0

    if yCount < 2 || xCount < 2 {
        for y in 0..<yCount {
            for x in 0..<xCount where copy[y][x] == 1 {
                max = 1
                break
            }
        }
    } else {
        for y in 1..<yCount {
            for x in 1..<xCount where copy[y][x] == 1 {
                copy[y][x] = min(copy[y - 1][x], copy[y][x - 1], copy[y - 1][x - 1]) + 1
                if copy[y][x] > max {
                    max = copy[y][x]
                }
            }
        }
    }
    
    answer = Int(pow(CGFloat(max), 2))

    return answer
}

자신의 왼쪽, 자신의 위쪽, 자신의 대각선 위쪽 숫자들중에 가장 작은 수에서 +1을 한 값을 자신의 값에 저장하는 방법으로 값을 구할수 있습니다.

 

이렇게 하면 자신 자체가 정사각형이 되면서 앞에 두개의 공간의 값을 가져와서 더해주면 됩니다.