[백준] 1915번 C/C++ 풀이 _ 가장 큰 정사각형

 


- 출처 : https://www.acmicpc.net/problem/1915 

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB89832653192928.710%

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0100
0111
1110
0010

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

예제 입력 1 

4 4
0100
0111
1110
0010

예제 출력 1 

4

알고리즘 분류



- 풀이


처음에 입력받은 0,1 매트릭스와 최대 정사각 행렬이 하나씩 필요합니다. 

최대 정사각 행렬의 첫행과 첫열은 0,1 매트릭스와 동일하게 세팅합니다. 

규칙은 위와 같습니다. 
갱신 위치의 0, 1 매트릭스 값을 확인합니다. 
0이면 최대 정사각 행렬도 0이고, 1이면 최대 정사각 행렬에서 빨간 인접한 부분의 값 중에서 가장 작은 값 + 1 을 해줍니다. 

원리는 그림을 보면, 맨 마지막 행과 열이 만나는 지점을 갱신 위치라고 가정합니다. 
갱신위치의 인접한 3개의 위치의 값은 0이 아니라면, 자신은 무조건 1입니다. 
그리고 최소 값이 

아래의 예시를 보면 약간 더 이해하기 쉽습니다. 


- 주의사항

n, m 이 1일 때, 처리를 하지 않아서 에러가 많이 났습니다. 

- 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#define MAX 1000
#pragma warning(disable : 4996)
using namespace std;
 
int matrix[MAX][MAX] = { 0 };
int answer[MAX][MAX] = { 0 };
int n, m;
int bigger = 0
 
int main(void) {
    cin >> n >> m;
    // matrix 행렬 초기화 
    for ( int n_idx = 0 ; n_idx < n ; n_idx++){
        for (int m_idx = 0; m_idx < m; m_idx++) {
            int sub;
            scanf("%1d"&sub);
            matrix[n_idx][m_idx] = sub;
        }
    }
 
    // answer 초기화  
    for (int n_idx = 0; n_idx < n; n_idx++)  answer[n_idx][0= matrix[n_idx][0] ? 1 : 0 ;
    for (int m_idx = 0; m_idx < m; m_idx++)  answer[0][m_idx] = matrix[0][m_idx] ? 1 : 0;
    // 1,1 에서 오류 방지하려면 초기화 필요
    bigger = answer[0][0];
 
    // 값 구하기 
    for (int n_idx = 1; n_idx < n; n_idx++){
        for (int m_idx = 1; m_idx < m; m_idx++) {
            //  1이 아니면 넘긴다. 
            if (matrix[n_idx][m_idx] == 1) {
                // 1이면 최소값 + 1 로 결정. 
                answer[n_idx][m_idx] = min({ answer[n_idx - 1][m_idx],
                    answer[n_idx][m_idx - 1], answer[n_idx - 1][m_idx - 1] }) + 1;
                if (bigger < answer[n_idx][m_idx])  bigger = answer[n_idx][m_idx];
            }
        }
    }
 
    cout << bigger*bigger;
 
    return 0;
}
 
 
cs