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

# 문제 원문

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

예를 들어

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

1234

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

 

# 문제 풀이

2차원 배열로 주어진 입력값 board에서 1로 이루어진 가장 큰 정사각형을 구하고 그 정사각형을 구성하는 갯수를 구하는 문제이다. 2차원 배열에 대해서 익숙하지 않으면 조금 헤맬 수 있는 문제인 것 같다. 처음 구상으로는 current 기준 오른쪽, 아래, 대각선 오른쪽 아래를 확인해서 전부 1이면 정사각형 count를 늘리는 방법으로 진행했으나, count 계산이 제대로 안되는 문제가 있어서 반대로 변경했다. 그리고 나서 테스트케이스 1이 실패하는 요인으로 최소크기 4만큼도 안되는 입력값일 경우 예외처리가 필요해서 해당 부분 처리했다. 솔직히 풀기는 했지만 아직도 머릿속에 선명하게 안떠오른다.. 관련 문제들을 조금 더 연습해야할듯하다.

# 솔루션 플로우

1. 입력 받은 board의 각 row를 순회한다.

2. 각 row의 매 col를 순회한다.

3. 해당 col이 1일 경우 해당 col기준 rdx - 1 과 cdx - 1까지 범위의 rdx, cdx가 모두 1인지 확인한다.

4. 정사각형이 맞을 경우 해당 col에 +1 해서 카운팅해준다.

5. 그후 result와 카운트를 비교해서 큰 수로 교체한다.

6. 예외 상황으로 최소크기의 4만큼도 안될 경우 체크하지 못하므로 result가 0 일시 result를 1로 변경해준다.

6. 얻어진 result를 2승해서(result * result) 반환한다. 

1. 반복문을 활용한 풀이

function solution(board) {
    return board.reduce((result, row, rdx) => {
        row.forEach((col, cdx) => {
            if (col > 0) {
                if (board[rdx - 1] !== undefined && row[cdx - 1] !== undefined) {
                    const state = Math.min(row[cdx - 1], board[rdx - 1][cdx], board[rdx - 1][cdx - 1]);
                    board[rdx][cdx] = state + 1;
                    result = (state + 1) < result ? result : (state + 1);
                } else if (result === 0) result = 1;
            }
        });
        return result;
    }, 0) ** 2;
}