가장 큰 정사각형

Created

2021/03/23 01:58

문제 번호

1915

카테고리

1915번: 가장 큰 정사각형

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/1915

Memo

BSQ 때 진행했던 문제와 동일

Map과 Memoization 벡터를 따로 둘 필요 없이 Map 벡터에 입력을 받으면 바로 Memoization을 Map 위에 수행하면 됨

주의할 점은 입력을 받을 때 공백 문자를 없이 받기 때문에 문자열로 입력을 받아 파싱해줘야 함

(x, y)

에 해당 좌표에서 만들 수 있는 가장 큰 정사각형 길이를 누적 받아가면 되는데, 이 때 비교 대상은 총 3개 →

(x - 1, y)

(x, y- 1)

(x - 1, y - 1)

정사각형이 아니라면 위 점들은 0을 갖고 있기 때문에 (x,y)(x, y)(x,y)에는 자기 자신인 111짜리 정사각형이 됨

정사각형이라면 위 점들도 각 점에서 만들 수 있는 최대 정사각형 길이를 갖고 있을 것이기 때문에, 3개의 점 중에서 최소 값이, (x,y)(x, y)(x,y)에서 이룰 수 있는 정사각형이 됨 (마찬가지로 자기 자신 길이 111을 더해줘야 함)

행이

n

, 열이

m

이었다면,

n \times m

의 반복 횟수안에 3개의 점에 대한 비교 구문만으로 정사각형 누적 최대 길이를 구해나갈 수 있음

각 Loop에서 비교 구문은 값이

0

이 아닐 때만 수행하면 됨 → 비교 후

+1

을 해주는 구문이

0

일 때도 수행되면, 결과보다 더 큰 값을 누적 받아오므로 정사각형으로 추정할 수 있는 값에 대해서만 수행해야 함

Code

제출 날짜

@2/24/2021

메모리

5996 KB

시간

8 ms

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

int		g_row;
int		g_col;
int		g_max;
std::vector<std::vector<int>> g_map;

void	pre_setting(void)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

void	input_action(void)
{
	std::cin >> g_row >> g_col;
	g_map = std::vector<std::vector<int>>(g_row + 1, std::vector<int>(g_col + 1, 0));
	for (int i = 1; i <= g_row; i++)
	{
		std::string tmp(g_col, '\0');
		std::cin >> tmp;
		for (int j = 0; j < g_col; j++)
			g_map[i][j + 1] = tmp[j] - '0';
	}
}

void	logic(void)
{
	for (int i = 1; i <= g_row; i++)
	{
		for (int j = 1; j <= g_col; j++)
		{
			if (g_map[i][j])
			{
				g_map[i][j] =
					std::min({ g_map[i - 1][j], g_map[i][j - 1], g_map[i - 1][j - 1] }) + 1;
				g_max = std::max(g_max, g_map[i][j]);
			}
		}
	}
}

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

void	solution(void)
{
	input_action();
	logic();
	output_action();
}

int		main(void)
{
	pre_setting();
	solution();
	return (0);
}
C++
복사