[c++] BOJ 1915 :: 가장 큰 정사각형

난이도 : 골드 5

걸린 시간 : 1시간 20분

 

문제

가장 큰 정사각형 문제 바로가기

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

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

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

 

풀이

• 작은 문제 : 현재 위치에서 오른쪽과 아래 방향으로 가질 수 있는 정사각형의 최대 크기
• 재귀식
  • 해당 위치에서 나타날 수 있는 최대 크기 정사각형의 한 변을 Area(row, col)이라고 한다면
  • Area(row, col) = min(Area(row+1,col)+1, Area(row,col+1)+1, Area(row+1,col+1)+1)
• 조건
  • 벽에 붙어있으면 Area가 1
  • 값이 0이면 Area가 0

 

코드

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int n, m;
int arr[1001][1001];
int memo[1001][1001]; // 정사각길이 저장
int maxNum = 0;

int area(int row, int col) {
    if (memo[row][col] != -1) // 메모이제이션
        return memo[row][col];

    if (arr[row][col] == 0) { // 값이 0이면 0
        memo[row][col] = 0;
        return memo[row][col];
    }

    if (row == n - 1 && col == m - 1) { // 벽에 붙어있으면 1
        memo[row][col] = 1;
        return memo[row][col];
    }

    int nextRow, nextCol, nextDiag;
    nextRow = area(row, col + 1) + 1;
    nextCol = area(row + 1, col) + 1;
    nextDiag = area(row + 1, col + 1) + 1;

    memo[row][col] = min(min(nextRow, nextCol), nextDiag);

    return memo[row][col];
}

int main() {
    // 입력
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            arr[i][j] = str[j] - '0';
        }
    }
    // 초기화
    memset(memo, -1, sizeof(memo));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int res = area(i, j);
            if (res > maxNum)
                maxNum = res;
        }
    }
    cout << maxNum * maxNum;
}

<arr 배열>

<memo 배열>

memo 배열 중 가장 큰 값의 제곱을 출력

 

결과

 

다른 사람의 풀이

벽에 붙어있는 값은 미리 memo 배열에 넣어두고, 재귀식을 이용하여 반복문으로 구성하면 시간을 더 줄일 수 있다.

https://howtolivelikehuman.tistory.com/209

https://bba-dda.tistory.com/entry/%EB%B0%B1%EC%A4%80C-1915-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95