(C++) 백준 1915번 [가장 큰 정사각형]

백준 1915번 문제 [가장 큰 정사각형] 알고리즘 포스팅을 시작해보겠습니다.

다이나믹 프로그래밍 문제인데, 처음에 다른 방식으로 풀었다가 시간초과가 나서 그제서야 DP로 방향을 잡고 풀었으나, 추상화와 해결방법을 쉽게 찾지 못하다가 겨우 푼 문제입니다.

 

골드 5 난이도의 문제입니다

 

---

1. 문제 해결 방법 구상하기

 - 입력값부터 받는 데 문제가 생깁니다. 그냥 cin 으로 해서 int값으로 입력받을 수는 없습니다.

 - 그렇다면 scanf를 이용하여 %1d 로 받을 수도 있고, 문자열 형태로 입력을 받은 후, -'0'을 해주어 int 값으로 다시 변환해줄 수도 있습니다.

 - 입력받은 후에 문제 해결은 어떻게 해야 할까요?

 - 다이내믹 프로그래밍이란 추상화, 즉 점화식이 굉장히 중요합니다.

위의 그림에서 가장 중앙에 있는 정사각형을 기준으로 왼쪽 위, 위, 왼쪽에 있는 세 개의 정사각형이 가운데에 있는 정사각형에 영향을 주게 됩니다. 여기서 세울 수 있는 점화식이 바로

 

map[r][c] = min(min(map[r][c - 1], map[r - 1][c]), map[r - 1][c - 1]) + 1;    입니다.

 

(원래 해당 정사각형의 값이 1이었다면) 만약 왼쪽 위, 위, 왼쪽 세 개의 정사각형이 모두 1 이라면 위의 점화식에 의해 해당 정사형에 들어갈 값은 2가 됩니다. 즉 그 정사각형에 대입되는 값은 그 정사각형을 기준으로 서북쪽으로 크기가 2*2만큼의 정사각형을 갖고 있다는 뜻이 되겠죠. 다른 정사각형도 마찬가지로 이 점화식이 성립합니다.

---

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int map[1001][1001] = { 0, }; // 여기서 1001 까지의 배열을 선언한 이유는 1행의 정사각형들과
							  // 1열의 정사각형들에 0값을 대입해주어야만 하는 이유가 있기 때문이다.
int maxlength = 0;			  // 왜냐하면 n과 m이 1인 경우를 생각해주어야 하기 때문이다.

void input()
{
	string num; //문자열 형식으로 입력받고 int형으로 변환해주었음.
	cin >> n >> m;

	for (int r = 1; r <= n; r++)
	{
		cin >> num;
		for (int c = 1; c <= m; c++)
		{
			map[r][c] = num[c - 1] - '0';
		}
	}
}

void solve()
{
	for (int r = 1; r <= n; r++)
		for (int c = 1; c <= m; c++)
		{
			if (map[r][c] == 1)
			{
				map[r][c] = min(min(map[r][c - 1], map[r - 1][c]), map[r - 1][c - 1]) + 1;
				maxlength = max(maxlength, map[r][c]);
			}
		}
}

void output()
{
	cout << maxlength * maxlength << endl; //정사각형의 넓이크기를 구해야 하므로 제곱해준다.
}

int main()
{
	input();
	solve();
	output();

	return 0;
}

확실히 DP는 정말 어려운 것 같습니다.  점화식 하나만 생각해내면 되는 문제임에도 골드 5 난이도가 부여됬다는 것은 그만큼 추상화라는 것, 즉 그 아이디어를 떠올리는 것이 정말 어렵기 때문이라고 생각합니다. 앞으로도 꾸준히 DP 문제를 접해야겠다고 생각했습니다.

 

/ /문제제기 및 피드백 언제든지 감사히 받겠습니다.