[코드트리 조별과제][C++] 격자 안에서 완전탐색 / 양수 직사각형의 최대 크기

[문제 출처]

https://www.codetree.ai/missions/2/problems/max-area-of-positive-rectangle/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 문제

설명

 

n * m크기의 이차원 영역의 각 위치에 정수 값이 하나씩 적혀있습니다. 이 영역 안에서 가능한 양수 직사각형 중 최대 크기를 구하려고 합니다. 양수 직사각형이란, 직사각형의 변들이 주어진 격자 판에 평행하면서, 직사각형 내에 있는 숫자들이 전부 양수인 직사각형을 의미합니다. 최대 크기의 양수 직사각형을 찾는 프로그램을 작성해보세요.

예를 들어 다음 그림의 경우에는, 크기가 6인 양수 직사각형을 찾을 수 있습니다.

 

입력 형식

첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄부터 (n+1)번째 줄까지는 각 행의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ n, m ≤ 20
• -1,000 ≤ 정수 값 ≤ 1,000

출력 형식

모든 값이 양수로만 이루어져 있는 직사각형 중 최대 크기를 출력해주세요. 만약 그러한 직사각형이 없다면, -1을 출력해주세요.

 

입출력 예제

예제1

입력:

3 3
1 2 3
3 4 5
6 7 8

 

출력:

9

 

예제2

입력:

4 5
6 -2 4 -3 1
3 6 7 -4 1
6 1 8 15 -5
3 -5 1 16 3

 

출력:

6

 

 

 

2. 설명

모든 경우의 수를 찾아보며 양수인 직사각형을 찾아보았습니다.

 

순서로는 메인문안에서 시작하는 y좌표, x좌표, 세로길이, 가로길이를 CalRect함수에 전달합니다.

 

함수안에서는

1. 받은 직사각형의 범위가 n*m크기를 벗어나는지 확인하고, 벗어나면 -1을 반환합니다.

2. 범위내의 모든 곳을 방문합니다. 이때 1보다 작은, 즉 양수가 아닌경우 바로 -1을 반환합니다.

3. 포문을 벗어나면 모든곳을 방문했을때 양수이므로 직사각형의 크기인 세로*가로를 반환해줍니다.

 

다시 메인문으로 돌아가서 계속해서 직사각형의 크기를 받아주며, 크기가 가장 큰것을 업데이트 해 줍니다.

 

3. 코드

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> maps;

int n, m;

int CalRect(int starty, int startx, int h, int w){

    if(starty+h<0 || starty+h>=n || startx+w<0 || startx+w>=m)

        return -1;

    for(int y=starty; y<=starty+h; y++)

        for(int x=startx; x<=startx+w; x++)

            if(maps[y][x]<1)

                return -1;

    return (h+1)*(w+1);

}

int main() {

   

    cin>>n>>m;

    maps.resize(n,vector<int>(m,0));

    for(int y=0; y<n; y++)

        for(int x=0; x<m; x++)

            cin>>maps[y][x];

    int max=-1;

    for(int y=0; y<n; y++)

        for(int x=0; x<m; x++)

            for(int h=0; h<n; h++)

                for(int w=0; w<m; w++){

                    int sum=CalRect(y,x,h,w);

                    if(max<sum)

                        max=sum;

                }

    cout<<max;

    return 0;

}