1915번: 가장 큰 정사각형

Memo

• 접근 방법

이차원 배열에 값을 저장해 놓습니다. 가로 세로 길이를 1씩 증가시킨 상태여야 하는데 그 이유는 코드의 일관성 때문입니다. 처음에 배열을 0으로 초기화 합니다. 그 후에 1,1 부터 N,N 까지 input을 받습니다.

1,1 부터 N,N 까지 각 행마다 각 열을 순회하는데, 현재 자신의 위치의 값이 0이라면 정사각형은 절때 만들어 질 수 없기 때문에 그 곳은 분기를 통해 지나치고, 현재 자신의 위치의 값이 1이라면 위, 왼쪽 위 대각선, 왼쪽을 검사하여 가장 작은 값에 1을 더한 값 을 저장합니다.

가장 작은 값을 선택하는 이유는, 현재 그 자리에 그 값이 왜 있는지를 생각해 보면 되는데, 조사하려고 하는 그 자리에 있는 값은 0을 만났을 때를 제외한 자신이 만들수 있는 가장 긴 길이의 정사각형 한 변이기 때문입니다. 따라서 그 변은 확정적으로 자신의 현재 위치에서 만들 수 있는 것입니다.

가장 긴 변을 순회하면서 계속해서 업데이트를 해나가면서, 최종적으로 가장 큰 정사각형의 넓이를 구해낼 수 있습니다.

Code

제출 날짜

2021/02/24

메모리

5996 KB

시간

12 ms

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::vector<int> > sq;
size_t n, m;
int g_max;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::string tmp;
	std::cin >> n >> m;
	sq.resize(n + 1, std::vector<int>(m+1));
	for (size_t i = 1 ; i < n + 1  ; i++)
	{
		std::cin >> tmp;
		for (size_t j = 1 ; j < tmp.size() + 1 ; j++)
			sq[i][j] = tmp[j - 1] - '0';
	}
	g_max = 0;
}

void logic()
{
	for (size_t i = 1; i < n + 1 ; i++)
		for (size_t j = 1 ; j < m + 1 ; j++)
		{
			if (!sq[i][j])
				continue;
			sq[i][j] = std::min({sq[i - 1][j], sq[i][j - 1], sq[i - 1][j - 1]}) + 1;
			g_max = g_max > sq[i][j] ? g_max : sq[i][j];
		}
}

void solve()
{
	logic();
	std::cout << g_max * g_max;
}

int main()
{
	input();
	solve();
	return (0);
}