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

코딩테스트 연습 - 가장 큰 정사각형 찾기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> board)
{
    int answer = board[0][0];

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

---

 다른 블로그들은 그림을 다 그린거 같은데 귀찮아서 제외하겠습니다...

 

 일단 배열에서 0이 아닌 부분은 사각형이 될 수 있으므로 이곳을 만나면 "왼쪽 대각선 위, 왼쪽, 위" 3군데를 보고 이중 최소값을 가져옵니다. 만일 0이 있다면 0을 고르게 되는 것이죠(정사각형이 될 수 없으니). 그런 다음 최솟값 + 1이 해당 지영에서 만들 수 있는 "가장 큰 사각형의 가로"가 됩니다. 이렇게 계속 누적을 시켜서 풀이를 하는 것이죠.

 아마 직접 그리면 더 이해가 잘 될거라고 봅니다.