프로그래머스: 연습문제 - 가장 큰 정사각형 찾기

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

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

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

---

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

풀이

혼자서 풀지 못해 다른 분들의 코드와 풀이를 사용했다.

2차원 배열 (1,1) 자리에서 부터 좌측 상단 방향으로 주변을 검사해서 제일 작은수를 (1,1) 자리에 더해주면서 2차원 배열을 동일한 방식으로 다 돌게 되면 제일 큰수가 생기고 이 큰수를 제곱한 값을 리턴

단, 행이나 열이 하나인 경우에는 1의 포함 여부로 리턴값을 결정한다.

자세한 설명은 이 게시글을 참고!

정답 코드는 이 게시글이 좀 더 직관 적인 듯

func solution(_ board: [[Int]]) -> Int {
    var arrays = board
    var max = 0

    if board.count == 1 {
        return board[0].contains(1) ? 1 : 0
    }

    if  board[0].count == 1 {
        return board.flatMap {$0}.contains(1) ? 1 : 0
    }

    for row in 1..<board.count {
        for column in 1..<board[0].count {
            if arrays[row][column] == 1 {
                let min = [arrays[row-1][column-1], arrays[row-1][column], arrays[row][column-1]].min()
                arrays[row][column] += min ?? 0
                max = (max > arrays[row][column]) ? max : arrays[row][column]
            }
        }
    }

    return max * max
}