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

문제 : 가장 큰 정사각형

문제 설명

 

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

 

예를 들어

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

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

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으로만 이루어져 있습니다.

 분석

 처음에 아무 생각없이 brute force로 풀었는데, 시간 초과가 나왔다. 즉, 이 문제는 동적 계획법 유형의 문제인 것이다. 이 문제는 정사각형의 좌하단이 핵심이다. 좌하단을 기준으로 값을 처리하면 가장 큰 정사각형의 크기를 구할 수 있다.

 

문제 처리 알고리즘

 계산하는 방식은 다음과 같다. 해당 좌하단 부분이 1이라면, 왼쪽과 상단 중 최솟값을 찾고, 그 최솟값과 좌상단 중 작은 값에 +1을 하면 된다. 몇 번 해보면 이해가 갈 것이다. 그렇게 되면 각 좌하단에서 생성이 가능한 최대 정사각형 길이를 알 수 있게 된다.

 

 구현

using namespace std;

int solution(vector<vector<int>> board)
{
	int ans = board[0][0];
	int y = board.size(), x = board[0].size();
	if (y <= 1 || x <= 1) return 1;

	for (size_t i = 1; i < y; i++)
	{
		for (size_t j = 1; j < x; j++)
		{
			if (board[i][j] == 1)
			{
				board[i][j] = min(board[i][j - 1], board[i - 1][j]);
				board[i][j] = min(board[i][j], board[i - 1][j - 1]) + 1;
				ans = max(ans, board[i][j]);
			}
		}
	}

	return ans * ans;
}

int main()
{
	vector<vector<int>> data = { {0,0,1,1},{1,1,1,1} };
	cout << solution(data);
	return 0;
}