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

문제 설명

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

제한사항

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

---

풀이

실패
모든 인덱스 순회하며 현재까지 저장된 max_len만큼의 정사각형이 만들어 질 수 있는지 체크하고, 만약 가능하다면 더 큰 정사각형이 될 수 있는지 탐색하는 코드를 작성했다. 행열의 크기가 1000이면 이렇게 풀어도 적당히 되지 않을까? 라고 안일하게 생각했던 것 같다. 결국 문제의 효율성 테스트는 통과할 수 없었으며, 풀이를 검색하게 되었다. 효율성 테스트를 통과하기 위한 풀이는 DP를 이용하는 것이었다.

1 1 1    1 1 1
1 1 1    1 2 2
1 1 1    1 2 3

(1,1)의 인덱스에서 보면, 위, 왼쪽, 왼쪽 대각선 위의 값이 1이어야 2x2의 정사각형이 만들어진다. (1,2)의 경우에는 왼쪽값은 2지만 왼쪽 대각선 위의 값과 위의 값이 1이므로, 여기서 만들어지는 최대 정사각형은 역시 2x2이다. 이와 같이 각 인덱스마다 위 , 왼쪽, 왼쪽 위의 3가지 값을 참고하여 만들어질 수 있는 정사각형 크기의 최대값을 저장하는 것이다.
풀이를 보고 이해할수는 있었지만, 문제를 풀면서 정사각형의 조건을 통해 DP풀이법을 떠올리는 것은 나에게는 아직 너무 어려운 일이었던 것 같다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> board){
    int max_len = 0;
    for(int i = 1; i < board.size(); ++i){
        for(int j = 1; j < board[0].size(); ++j){
            if(board[i][j] == 1){
                board[i][j] = min(board[i-1][j-1], min(board[i][j-1],board[i-1][j])) + 1;
            }
        }
    }
    
    for(int i = 0; i < board.size(); ++i){
        for(int j = 0; j < board[0].size(); ++j) max_len = max(max_len, board[i][j]);
    }
    
    return max_len*max_len;
}