leetcode 221) Maximal Square

LV. Medium 🧐

https://leetcode.com/problems/maximal-square/

Maximal Square - LeetCode

 

문제

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'

 

문제 해결법

dp로 해결하면 된다

{ {1, 1, 1},

{1, 1, 1},

{1, 1, 1}} 이 들어오면 아래와 같이 배열이 만들어진다

1	1	1
1	1	1
1	1	1

dp로 문제를 풀기 위해 아래와 같이 (m + 1) * (n + 1) 크기의 배열을 만들고 x = 0, y = 0인 부분은 0으로 채운다

0	0	0	0
0
0
0

if (matrix[y][x] == 1) 일 때 dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]의 최솟값에 1을 더해 dp[y][x]를 채워준다

 

그럼 왜 dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]의 최솟값에 1를 더할까?

dp[y][x]입장에서 자신이 1일 때 자기 앞단에서 정사각형의 최댓값이 몇이 나왔는지 알아야 된다

1. dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]의 최솟값이 0이라면 앞에 정사각형이 전혀 없는 것이기 때문에, 자기 자신 1이 정사각형의 최댓값이다

2. dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]의 최솟값이 3이라면 앞에 정사각형이 끊기지 않고(matrix[y][x] == 1일 때만 최솟값 + 1을 해주므로 정사각형이 끊기질 않음을 확인할 수 있음) 3*3까지 만들어졌음을 알 수 있다

 

해결 코드

#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
	int ans;
	int m;
	int n;
	vector< vector<int> >dp;

public:
	int maximalSquare(vector< vector<char> >& _matrix) {
		m = _matrix.size();
		n = _matrix[0].size();
		ans = 0;
		dp.assign(m + 1, vector<int>(n + 1, 0));

		for (int i = 0; i <= m; ++i)
			dp[i][0] = 0;
		for (int j = 0; j <= n; ++j)
			dp[0][j] = 0;

		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (_matrix[i - 1][j - 1] == '1') {
					dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]) + 1;
					ans = max(ans, dp[i][j]);
				}
			}
		}
		return ans * ans;
	}
};