- 출처 : https://www.acmicpc.net/problem/1915
가장 큰 정사각형 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 8983 | 2653 | 1929 | 28.710% |
문제
n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
위와 같은 예제에서는 가운데의 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 |