[백준] 4095 최대 정사각형

⚡백준 4095 최대 정사각형

• https://www.acmicpc.net/problem/4095

• 첫 번째 코드 (시간 초과)

#include <iostream>
#include <algorithm>
using namespace std;

int matrix[1001][1001];

bool isSquare(int r, int c, int len) {
	bool square = true;
	
	for(int i = r; i < r + len; ++i)
		for (int j = c; j < c + len; ++j)
			if (matrix[i][j] == 0) {
				square = false;
				break;
			}

	return square;
}

int maxSquare(int n, int m) {
	//길이가 큰 정사각형부터 탐색
	for(int len = min(n, m); len > 0; --len)
		for(int r = 0; r + len -1 < n; ++r)
			for (int c = 0; c + len - 1 < m; ++c) {
				//정사각형의 네 모서리 검사
				if (matrix[r][c] == 0) continue;
				if (matrix[r + len - 1][c] == 0) continue;
				if (matrix[r][c + len - 1] == 0) continue;
				if (matrix[r + len - 1][c + len - 1] == 0) continue;

				if (isSquare(r, c, len)) return len;
			}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0)
			break;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				cin >> matrix[i][j];

		cout << maxSquare(n,m)<<"\n";
	}

	return 0;
}

풀이

• 동적 계획법
  -> dp[i][j]: (i,j)로 끝나는 최대 정사각형의 한 변 길이

• 이때, 전체 NXM 행렬의 맨 위 행과 맨 오른쪽 열을 처리하는 경우에 주의하여 코드를 짜야한다

• ex. 6 6
  1 0 0 0 0 0
  0 0 0 0 0 0
  1 0 0 0 0 0
  0 0 0 0 0 0
  0 0 0 0 0 0
  0 0 0 0 0 0
  wrong: 0
  answer: 1

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1002][1002] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0)
			break;

		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				cin >> dp[i][j];

		int res = 0;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				if (dp[i][j] == 0) continue;

				dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j-1]) + 1;
				res = max(res, dp[i][j]);
			}
		cout << res << "\n";
	}

	return 0;
}

📌참고자료

• 백준 4095 최대 정사각형 풀이
  https://ans2552.tistory.com/8?category=948306