[Swift - 프로그래머스] 가장 큰 정사각형 찾기

🕵🏻  문제 해석

---

1과 0으로 채워진 표가 주어지면 그 표에서 1로 이루어진 가장 큰 정사각형의 넓이를 반환하는 문제입니다. 단, 정사각형은 축과 평행해야 합니다.

예시로 주어진 4 X 4의 표에서는 가장 큰 정사각형의 넓이가 9가 되겠습니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1 또는 0으로만 이루어져 있습니다.

먼저 가장 작은 크기의 정사각형으로 부터 크기를 확장하며 문제에 접근해보겠습니다. 가장 작은 크기의 정사각형은 1 X 1 크기의 1로 이루어진 정사각형이겠죠? 그다음 크기의 정사각형은 2 X 2의 1로 이루어진 정사각형입니다. 

이렇게 4 X 4 크기의 표가 주어졌다고 생각해봅시다. 파란색으로 표시된 (1 , 1) 위치를 정사각형의 우하단 꼭지점이라고 생각하고, 1로 이루어진 2 X 2 크기의 정사각형 있는지 판단하기 위해서는 빨간색으로 칠해진 (0, 0), (0, 1), (1, 0) 위치의 숫자가 모두 1 인지를 판단해야 합니다.  만약 빨간색 위치의 숫자가 모두 1이라면 2 X 2 크기의 정사각형이 될 것이고 그렇지 않다면 파란색 위치의 1로만 이루어진 1 X 1 크기의 정사각형이 될 것입니다. 

이런 방식으로 확장해 나가기위해 해당 좌표를 1로 이루어진 정사각형의 우하단이라고 생각하고 그 좌표의 값에 정사각형의 최대 변의 크기를 저장하는 Square 배열을 만들어 봅시다. 

Board배열을 복사한 Square 배열입니다. Square 배열에는 해당 좌표를 정사각형의 우하단이라고 하였을 때 가장 큰 정사각형의 변의 길이를 저장하는 배열입니다. 

그렇다면 조금 더 확장해서 (R, C)에서 1로 이루어진 3 X 3 크기의 정사각형이 되려면 어떻게 되어야 할까요?

( R - 1 , C ), ( R - 1, C - 1 ), ( R , C - 1 ) 이 세 좌표를 정사각형의 우하단으로 하는 2 X 2 정사각형이 3개가 존재하면 됩니다.

빨간색, 파란색, 초록색 테두리의 2 X 2 정사각형이 존재하면 Board배열에서 파란색으로 칠해진 좌표는 Square 배열에서 3의 값을 가지게 됩니다. 그러나 ( R - 1 , C ), ( R - 1, C - 1 ), ( R , C - 1 ) 이 세 좌표를 우하단으로 하는 정사각형들의 변의 최소 크기가 1이기 때문에 지금 파란색으로 칠해진 좌표의 Square배열의 값은 2가 됩니다.  이런 식으로 확장하면 최종적인 Square 배열의 값이 아래와 같이 갱신되게 됩니다.

설명한 대로 Square 배열에 정사각형의 최대 변의 크기를 갱신하여 저장하기 위해 Board배열을 탐색하며 Square 배열을 갱신해보겠습니다.  Board 배열을 순차적으로 탐색하면서 해당 좌표의 숫자가 1이라면 해당 위치의 Square 배열에서 빨간색 위치에 해당하는 Square배열의 값 중 최솟값을 더하여 값을 저장합니다. 

for row in 1..<board.count {
    for col in 1..<board[row].count {
        if board[row][col] == 1 {
            square[row][col] += min(square[row-1][col], square[row-1][col-1], square[row][col-1])
            maxVal = max(maxVal, square[row][col])
        }
    }
}   

 

이런 방식으로 Board 표를 탐색하며 Square 배열을 갱신하고 Square 배열의 가장 큰 값을 구하면 우리가 찾으려는 가장 큰 정사각형의 변의 길이를 찾을 수 있습니다.

그리고 주어진 Board의 행의 크기가 1이거나 열의 크기가 1인 경우 예외적으로 처리를 하여 답을 구하면 될 것 같습니다.

 

🤷🏻‍♂️  더 생각해보기

---

지금 행의 크기가 1이거나 열의 크기가 1일 경우 무조건 가장 큰 정사각형의 크기를 1로 리턴하여도 정답 처리되는 문제가 있습니다. 이 두 경우에서 모든 숫자가 0이라면 가장 큰 정사각형의 크기를 0으로 리턴해야 맞기 때문입니다. 프로그래머스에서 예외처리를 위한 테스트 케이스를 추가해야 할 듯싶습니다. 

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ board:[[Int]]) -> Int
{
    var maxVal = 0
    var square = board
    
    // 행의 크기가 1이거나 열의 크기가 1인경우
    if board.count == 1 || board.filter({$0.count > 1}).count == 0 {
        // 1을 하나라도 포함 하면 return 1
        for row in 0..<board.count {
            for col in 0..<board[i].count {
                if board[row][col] == 1 {
                    return 1
                }
            }
        }
        // 그렇지 않다면 0
        return 0
    }
    
    for row in 1..<board.count {
        for col in 1..<board[row].count {
       
            // 해당 좌표가 1이라면
            if board[row][col] == 1 {
            
                // 세 좌표를 우하단으로 하는 정사각형 변의길이의 최솟값을 더해준다.
                square[row][col] += min(square[row-1][col], square[row-1][col-1], square[row][col-1])
                
                // 최댓값 갱신
                maxVal = max(maxVal, square[row][col])
            }
        }
    }
    // 제곱하여 크기를 구한다.
    return maxVal * maxVal
}