[SWEA 4062] Largest Empty Square - C++

SW Expert Academy

 

 

문제

주어진 N*N흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형을 찾으시오.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)
각 테스트 케이스 첫째 줄에는 전체 맵의 크기 N이 주어진다(1 ≤ N ≤ 1,000).
그 다음 N줄에 걸쳐서 N개의 ‘0’또는 ‘1’이 입력된다. ‘0’은 비어있는 칸을 뜻하고, ‘1’은 검은 점을 뜻한다.

풀이

#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
int N;
int field[1001][1001] = { 0 };
int dp[1001][1001] = { 0 };
int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> N;
        string line;
        for (int i = 0; i < 1001; i++)
        {
            for (int j = 0; j < 1001; j++)
            {
                field[i][j] = 0;
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i < N + 1; i++)
        {
            cin >> line;
            for (int j = 1; j < N + 1; j++)
            {
                field[i][j] = 1 - int(line[j - 1] - '0');
            }
        }
        int answer = 0;
        for (int i = 1; i < N + 1; i++)
        {
            for (int j = 1; j < N + 1; j++)
            {
                if (field[i][j] == 1)
                {
                    dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
 
                    answer = max(answer, dp[i][j]);
                }
            }
        }
        cout << "#" << test_case << " " << answer << endl;
 
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

해결방법

DP를 활용하여 해결할 수 있는 문제입니다. 해당 문제는 백준에서도 주어지는 가장 기본적인 유형 문제이므로 해당 문제 풀이 방법에 대해서 잘 모르겠으면 가장 큰 정사각형(1915) 문제를 풀어보는 것을 권장합니다.