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

 

프로그래머스

 

 

정사각형에 2차원 배열인거 보고 분할정복 생각했지만 천천히 다시 읽어보니 관련 없는 문제였다

 

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

 

위에서 우하단을 기준으로 좌상단, 우상단, 좌하단이 1이상이면 정사각형

여기서 우하단에 네 값 중 가장 작은 값 + 1을 하면 해당 정사각형의 한 변의 길이가 됨

 

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 row = board.size();
    int col = board[0].size();
    
    // (1, 1)부터 시작 > 우하단을 기준으로 하기 때문
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
        	//0이면 정사각형이 불가능하고 1보다 크면 이미 확인한 구간이지만 중복된 구간을 체크하지 않기 때문에 1보다 클 일이 없음
            if(board[i][j] == 1) {
                board[i][j] = min({board[i-1][j-1], board[i-1][j], board[i][j-1]}) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }

    return answer * answer;
}