1915번: 가장 큰 정사각형

문제접근🤔

• dp에 무엇을 담을까 고민을 함

  그 위치에서 최대로 만들 수 있는 정사각형의 한변의 길이를 담으면 되겠다 판단

  

  예를들어, dp[2]2에 들어가게 될 녀석들을 생각해보면

  

  

  0인 부분엔 그릴 수 없기 때문에 위와 같이 두가지의 경우가 나옴

  따라서 dp[2]2엔 1이 들어가게 됨

  → 현재 위의 그림은 dp에 관련된 행렬이 아니라 처음에 입력 받은값에 관련된 행렬이기 때문에 주의

  dp행렬은 밑에서 그릴 예정

• 점화식 찾기

  <input행렬>

  

  우리가 a를 기준으로 최대정사각형을 만든다고 했을때 우리는 b c d 에도 그릴 수 있는지, 즉 0이 아닌지(사각형을 그릴 수 없는지)를 판단해줘야함

  위의 방식으로 dp행렬을 만들어보면

  <dp행렬>

  

  이런 형태가 나오게 되고, 빨간부분 과 파란부분 을 봐야함

  1. 빨간부분
     • 좌측,좌대각선,위가 모두 1(사각형을 그릴 수 있는 상태)
  2. 파란부분
     • 좌측,좌대각선,위 모두 사각형을 그릴 수 있는 상태
     • input을 보면 그 지점 자체가 0으로 사각형을 그릴 수 없기 때문에 dp[3]4은 0

  좌측, 좌대각선, 위 중 하나라도 사각형을 그릴 수 없으면 정사각형을 완성시킬 수 없기 때문에 셋 중에서 최솟값에 +1이 되는 형태

  $dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1(input[i][j] != 0일때)$

• 고려한점

  1. <dp행렬>

     

     파란 부분의 경우 점화식대로 풀 수가 없기 때문에(좌측, 좌대각선, 위가 존재하지 않음) input을 그대로 적어놓으면 됨

     결과적으로 파란색 이외의 부분만 구하면 됨

  2. 입력

     string으로 입력 받고 한글자씩 int로 변환하여 넣어줌

//pseudo code
vector<vector<int> > dp
int n,m

cin >> n,m
cin >> dp

while //n+1행부터
	while //m+1열부터

놓쳤던 부분😅

1. 최대 길이를 구하는 것이 아니라 최대 넓이를 구하는 것

   최대 길이를 구했기 때문에 제곱하면 됨

2. 최대 길이를 구하는 조건

   			if (i == 0 || j == 0)
   			{
   				max = std::max(dp[i][j], max);
   				continue ;
   			}
   

   나의 코드에서는 [1][어디든] [어디든][1] 은 입력 받은 결과 그대로를 쓰기 때문에 저 인덱스들에 대해서는 max값이 업데이트가 되지 않음

   예를들어

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

   에서 1을 업데이트 하지 못하고 max = 0이 되어 버리기 때문에 조건을 추가해야함

코드😁

5996 KB

12 ms

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

int n,m;
std::vector<std::vector<int> > dp;

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

void input()
{
	int i;
	int j;
	std::string input_arr;

	i = 0;
	std::cin >> n >> m;
	dp.resize(n + 1, std::vector<int>(m + 1));
	while (++i <= n)
	{
		j = 0;
		std::cin >> input_arr;
		while (++j <= m)
			dp[i][j] = input_arr[j - 1] - '0';
	}
}

void solution()
{
	int i;
	int j;
	int max;

	i = 0;
	max = 0;
	while (++i <= n)
	{
		j = 0;
		while (++j <= m)
		{
			if (dp[i][j] == 0)
				continue ;
			if (i == 0 || j == 0)
			{
				max = std::max(dp[i][j], max);
				continue ;
			}
			dp[i][j] = std::min(std::min(dp[i][j - 1], dp[i - 1][j - 1]), dp[i - 1][j]) + 1;
			max = std::max(dp[i][j], max);
		}
	}
	std::cout << max * max;
}

int main(void)
{
	input_setting();
	input();
	solution();
	return (0);
}