백준 1915번 가장 큰 정사각형

< 백준 1915번 가장 큰 정사각형 - 마포 코딩박 >

사용한 알고리즘: DP


 NxM 그리드가 주어졌을 때 1로 이루어진 최대 정사각형을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 9~10)
 'dp[x][y] : (x,y) 을 오른쪽 모서리로 하는 최대 정사각형의 한변의 길이' 라고 설정했습니다.

(2) (코드 17~30)
 그리드를 (0,0), (0,1), ... , (N-1,M-1) 순으로 방문해 보면서 dp 값을 구해줍니다.
 dp[x][y] 를 구하기 위해서는 이전에 구해놨던 dp[x-1][y-1], dp[x][y-1], dp[x-1][y] 중 작은값에 +1 해주면 됩니다. 즉, (x,y) 를 오른쪽 모서리로 하고, (x,y) 를 기준으로 왼쪽 대각선, 왼쪽, 오른쪽 으로 얼마나 갈 수 있는지를 생각해주면 됩니다.

	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	const int MAX = 1000;
	int N, M, ans;
	string arr[MAX+1];
	// 최대 사각형 한변
	int dp[MAX+1][MAX+1];
	int main(){ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for(int i=0; i<N; ++i) cin >> arr[i];
	for(int i=0; i<N; ++i){
	for(int j=0; j<M; ++j){
	// (i,j)가 1인 지점만 정사각형을 만들어본다.
	if(arr[i][j]=='1'){
	// (0,0)인 지점
	if(i==0 || j==0) dp[i][j] = 1;
	// 먼저 탐색했던 왼쪽 대각선, 왼쪽, 위를 둘러본다
	else
	dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]));
	// 각 지점마다 ans 값 최신화
	ans = max(ans, dp[i][j]);
	}
	}
	}
	cout << ans*ans << '\n';
	return 0;
	}

view raw BOJ 1915.cpp hosted with ❤ by GitHub