[백준][1915번] 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

문제풀이

 

dp[i][j]에는 i, j가 우측 하단에 위치한 정사각형의 크기를 점화식으로 세웠다.

 

예를 들면, i, j가 가장 우측 하단이 되는 경우는 아래와 같다.

i -1 , j - 1	i -1, j
i, j -1	i, j

3가지 경우를 체크하여 최솟값을 구해 1을 더해주면 현재 값의 정사각형의 제곱근을 구 할 수 있다.

 

현재 위치의 값이 0이면 처리 할 필요가 없으며, 1이지만 정사각형이 되지 않을 경우에 대한 처리도 생각해야 한다.

 

소스코드

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int N, M;
int map[1001][1001];
int dp[1001][1001];
int dx[3] = { -1, -1, 0 };
int dy[3] = { 0, -1, -1 };
int main()
{
	int answer = 0;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			map[i][j] = str[j] - '0';
		}
	}
	for (int i = 0; i < M; i++) {
		dp[0][i] = map[0][i];
		answer = max(answer, dp[0][i]);
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) continue;
			int minVal = 0x7fffffff;
			int isSquare = 1;
			for (int k = 0; k < 3; k++) {
				int nx = j + dx[k];
				int ny = i + dy[k];
				if (nx < 0 || ny < 0 || nx >= M || ny >= N) {
					isSquare = 0;
					break;
				}
				else {
					minVal = min(dp[ny][nx], minVal);
				}
			}
			dp[i][j] = isSquare ? minVal + 1 : 1;
			answer = max(answer, dp[i][j]);
		}
	}

	printf("%d\n", answer*answer);
	return 0;
}

 

결과