[백준 알고리즘] 1915번: 가장 큰 정사각형

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

문제

문제

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개의 숫자로 배열이 주어진다.

출력

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

풀이

다이나믹 프로그래밍으로 풀 수 있는 문제였다. 이제 어느정도 DP에 대한 감이 생겨서 이 문제는 혼자 힘으로 큰 어려움 없이 풀 수 있었다! 나도 조금씩은 성장하고 있나보다..

좌표 위에서 정사각형의 크기가 커지는 조건은 어떤 지점에서 왼쪽, 위, 대각선의 좌표가 1로 채워져 있는 경우이다. 그래서 각 좌표에는 해당 좌표에서 만들 수 있는 정사각형의 최대 길이를 저장하도록 하고, 왼쪽, 위, 대각선 위의 좌표에 0이 아닌 값들이 들어있고, 현재 좌표 역시 0이 아닐 때, 위 3개의 좌표의 값 중 가장 작은 값의 1을 더한 값을 해당 좌표에서 만들 수 있는 정사각형의 최대 길이로 설정했다. 이때 가장 작은 값을 취하는 이유는, 정사각형이 되려면 각 좌표들이 가진 공통된 길이 중 최장 길이를 구해야 하기 때문이다. 더 쉽게 이야기해보면, 현재 좌표에서 왼쪽 좌표에서 만들 수 있는 정사각형의 길이가 3, 대각선 위 좌표에서 만들 수 있는 정사각형의 길이가 3, 위쪽 좌표에서 만들 수 있는 정사각형의 길이가 2라면, 현재 좌표에서는 아무리 길어도 위쪽 좌표의 최장 길이를 초과하는 정사각형은 만들 수 없기 때문에, 현재 좌표에서 만들 수 있는 정사각형의 최대 길이는 2 + 1 인 3이 된다.

예외적으로 고려해야할 케이스는 판이 모두 0으로 채워져 있는 경우와 한칸짜리 정사각형만 존재하는 경우이다. 이를 처리하기 위해서 최장 길이를 저장하는 ans 변수는 초기에 0으로 초기화를 하고, 입력을 받을 때 1이 한번이라도 나타나면 1로 값을 바꿔주도록 했다. 이후에는 DP 를 통해서 최대 값이 업데이트 되기 때문에 여러칸으로 만들 수 있는 정사각형이 없을 때, 1이 판 위에 하나라도 존재하면 1이 출력되고, 0으로만 채워져 있다면 0이 출력될 것이다.

코드

' '
#include <cstdio>
#include <algorithm>

using namespace std;

int map[1001][1001];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int ans = 0;
    for (int i = 0;i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
            if (map[i][j] == 1) ans = 1;
        }
    }

    for (int i = 1;i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (map[i][j] != 0 && map[i - 1][j] != 0 && map[i - 1][j - 1] != 0 && map[i][j - 1] != 0) {
                map[i][j] = min(map[i - 1][j], min(map[i - 1][j - 1], map[i][j - 1])) + 1;
                ans = max(ans, map[i][j]);
            }
        }
    }
    printf("%d", ans * ans);
}