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

문제 :

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

예를 들어

1234

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

가 있다면 가장 큰 정사각형은

1234

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

방법 :

 * 동적계획법 (DP:Dynamic Programming)를 이용해서 푼다.

노랑색 칸의 좌측, 상단, 좌측상단 값 중에서 최솟값을 골라 +1해주면 노랑색 칸이 된다. 

위 그림에서 나올 수 있는 최대 정사각형의 한 변의 길이는 1이다.

 

1. board[1][1]부터 시작을 해서 board의 값이 1인지 확인을 한다.

   (왜 board[1][1]부터 인가? 좌측,상단,좌측상단이 없기 때문이다.)

2. 값이 1이면 좌측,상단,좌측상단 값 중에서 최솟값을 골라서 1을 더해준다.

3. 현재 board에 최솟값+1을 갱신하고 기존의 최대 변의 길이와 비교하여 변의 길이의 최댓값도 갱신해준다.

 

결과

 

코드 :

#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[0].size(); j++){
            if(board[i][j]){ 
                board[i][j] = min(board[i][j - 1], board[i - 1][j]);
                board[i][j] = min(board[i - 1][j - 1], board[i][j]) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}