[개쉬운 풀이] 백준 1915 가장 큰 정사각형 (CPP/C++)

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

1915번: 가장 큰 정사각형

생각

정사각형은 무엇인가? 모든 변의 길이가 같고 모든 각이 직각을 이루는 사각형이다.

근데 문제에 각은 90도로 고정이 된 상태이고 길이만 생각을 하면 되겠구나!

그렇다면 좌측 상단부터 우측 하단으로 이동하면서 각 위치에서 만들 수 있는 가장 큰 정사각형을 구하고 마지막에 어떤 크기가 가장 큰지 보면 되겠구나라고 생각하였다.

여기서 문제는 각 위치에서 만들 수 있는 가장 큰 정사각형을 어떻게 구하냐이다.

 

나의 결론은 다음과 같다.

1. 정사각형을 이루기 위해서는 0이 존재해서는 안된다.
2. 각 위치를 dp형태로 만들 수 있는 가장 큰 정사각형을 저장하여 다음 위치에서 계산을 할 때 재계산하지 않도록 한다.
3. 각 위치에서 가장 큰 정사각형 구하기 (예시)
   1. 현재 위치는 항상 정사각형의 우측 하단 이므로 파란색의 위치를 기준으로 정사각형의 최대를 구해보자
   2. map을 기준으로 현재 파란색의 위치는 1이다.
   3. 파란색의 위치를 기준으로 좌측 상단의 최대 정사각형 넓이를 구하므로 dp를 이용하여 빨간 밑줄 위치의 dp 정보를 이용하자.
      1. 왼쪽[r][c-1]과 위쪽[r-1][c]은 현재 길이가 2인 넓이의 정사각형이 최대이다. (왼쪽으로 최대 2길이 만큼 사각형 이용가능하다는 뜻)
      2. 좌측 상단 [r-1][c-1]은 현재 길이가 1인 넓이의 정사각형이 최대이다.
      3. 따라서 위 3가지의 정보를 가지고 최대 넓이를 찾아야한다.
         1. (조건) 만약 3가지 정보가 모두 2로 동일하다면 파란색의 위치에서 만들 수 있는 최대의 사각형은 3의 길이를 가진 정사각형이다.
         2. (조건) .만약  1가지 정보라도 작은 것이 있다면 그럼 최대 길이가 가장 작은 길이를 고려하여 3가지 정보 중 "가장 작은 정보 길이 + 1의 길이"를 가진 정사각형이 파란색의 위치에 해당하는 정보가 된다.
         3. 결론 : 3가지 고려해서 최소 정보 + 1 하면 현재 파란색의 정보임 
            1. (조건이 두가지 이지만 어차피 첫번째 조건은 모두 동일한 정보일때이므로 가장 작은 정보와 동일하기에 코드 단축)

 

코드

int n, m;
int map[1001][1001];
int dp[1001][1001];

void sol(){
	//i와 j를 1부터 탐색하는 이유는 어차피 그들은 왼쪽 상단이 없기 때문
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
        	//현재 위치가 1인가? (조건 1)
            if(map[i][j]){ 
            	//빨간색에 해당하는 3가지 정보 모두 1인가?
                if(map[i-1][j-1] && map[i-1][j] && map[i][j-1]){ 
                   	int minValue = 10e8;
                    minValue = min(minValue, dp[i-1][j-1]);
                    minValue = min(minValue, dp[i][j-1]);
                    minValue = min(minValue, dp[i-1][j]);
                    dp[i][j] = minValue + 1;   
                }
                //아니면 그냥 원래 배정받은 숫자가 최대(1)
            }
        }
    }
    int result = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(dp[i][j] > result) result = dp[i][j];
        }
    }
    cout << result*result << endl;
}

최대 정사각형을 구하는 방법만 고려한다면 쉽게 풀 수 있다.

마지막에 우리는 길이를 기준으로 구했으니 문제 출력 조건인 넓이(길이 * 길이) 반환

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int map[1001][1001];
int dp[1001][1001];


void input(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            map[i][j] = c - '0';
            dp[i][j] = map[i][j];
            
        }
    }
}

void sol(){
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
            if(map[i][j]){
                if(map[i-1][j-1] && map[i-1][j] && map[i][j-1]){ 
                    int minValue = 10e8;
                    minValue = min(minValue, dp[i-1][j-1]);
                    minValue = min(minValue, dp[i][j-1]);
                    minValue = min(minValue, dp[i-1][j]);
                    dp[i][j] = minValue + 1;
                    
                }
            }
        }
    }
    int result = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(dp[i][j] > result) result = dp[i][j];
        }
    }
    cout << result*result << endl;
}

int main(){
    input();
    sol();
    return 0;
}