알고리즘 문제 풀이 - 가장 큰 정사각형 찾기

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

가장 큰 정사각형 찾기

문제 설명

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합니다.

---

문제 풀이

function solution(board)
{
    var answer = 0;
    let n = board.length
    let m = board[0].length
    
    if(n<2 || m < 2) return 1;
    
    for (let i = 1; i<n; i++) {
        for (let j = 1; j<m; j++) {
            if(board[i][j]) board[i][j] = Math.min(board[i][j-1],board[i-1][j-1],board[i-1][j]) +1
            if(answer< board[i][j]) answer = board[i][j]            
        }
    }

    return answer*answer;
}

처음에는 가장 큰 정사각형일 때 0이 존재하면 안되는 식으로 진행을 하려했으나
이 문제풀이로는 해결할 수 없었다. 다른 방법을 고민해봤지만 결국 해결하지 못하고 다른 분들의 풀이를 확인했고 DP를 이용해서 문제를 풀어야하는 것을 깨달았다.

좌표 [1,1] 부터 좌,상,좌상이 1일 경우 2X2의 정사각형이 완성되는 것이기 때문에 [1,1]을 2로 바꿔준다. (2는 한변의 길이)

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

예시에 나와있는대로 3번과 4번이 2로 바뀌게 되고 다음으로 내려가서 진행을 계속하면

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

이렇게 되는데 [2,3] 좌표의 경우 좌, 상, 좌상이 모두 2이기 때문에 3X3 정사각형이 완성되고 3으로 바뀌게 된다. 마지막에 가장 큰 수를 제곱하면 정답이 나온다.