[Lv 2] 가장 큰 정사각형 찾기

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

프로그래머스

 

이 문제는 탐색을 통해 해결할 수 있다.

가장 큰 정사각형을 찾는 방법은 다음과 같다.

2차원 배열을 순회하며 정사각형의 후보가 될 수 있는 1을 찾는다.

이후 좌, 우, 위를 보고 1이상의 값이 있는 경우 1을 누적한다.

 

위 알고리즘을 따르면 테스트 케이스는 다음과 같이 변한다.

 

초기

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

 

최종 모습

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

 

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

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

    return answer*answer;
}