[C++] 백준 1915: 가장 큰 정사각형

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

 

 

문제 이해

n * m의 0과 1로 구성된 배열이 있을 때

1로만 이루어진 정사각형 중 가장 큰 것의 넓이를 구하는 문제입니다.

 

n, m : 1 ~ 10^3

 

 

 

완전 탐색으론 시간 초과가 났기에, DP를 사용해야겠다는 생각을 했는데 도저히 점화식을 못 찾았습니다.

 

도저히 감이 안 잡혀서 다음 포스트를 참고하고 풀었습니다.

 

https://yabmoons.tistory.com/158

[ 백준 1915 ] 가장 큰 정사각형 (C++)

 

진짜 이런 점화식은 어떻게 생각해내는 건지 궁금합니다... 공부를 더욱 열심히 해야겠습니다.

 

 

 

문제 풀이

먼저 입력을 받을 때, 배열이 띄어쓰기가 되어있지 않으므로,

string으로 받아서 처리하든, char형으로 받아서 처리하든 숫자로 바꾸는 전처리를 해줘야합니다.

 

cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char tmp;
            cin>>tmp;
            map[i][j] = tmp - '0';
        }
    }

 

저는 다음과 같이 진행했습니다.

 

 

그 다음이 핵심인데, 점화식만 먼저 봅시다.

map[i][j] = min(min(map[i-1][j-1], map[i-1][j]), map[i][j-1]) + 1;

위와 같은 점화식을 통해 문제를 해결할 수 있습니다.

이는 한 좌표의 대각선 위, 바로 위, 바로 왼쪽이 모두 1일 때 정사각형의 길이를 +1 해주는 겁니다.

 

 

주어진 예제를 통해 점화식에 대해 이해해보겠습니다.

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

 

처음 좌표를 (1,1), 끝 좌표를 (4,4)라고 가정하고 문제를 풀어보겠습니다.

 

 

배열 중 1의 값을 가지는 것만 생각을 해보면,

(2,2)에서는 min(min(0, 1), 0) =  0이 되고, +1을 하여 1의 값을 가집니다.

실제로도 정사각형은 1의 길이만을 가집니다.

 

 

(3,3)에서는 min(min(1, 1), 1) = 1이 되고, +1을 하여 2의 값을 가집니다.

왼쪽 대각선 위, 바로 위, 바로 왼쪽이 모두 1을 가지므로 정사각형의 길이가 1이 늘어난 것입니다.

0	1	0	0
0	1	1	1
1	1	2	0
0	0	1	0

 

조금 이해가 되시나요?

 

 

저는 이 점화식을 보며 놀랬던 것이

오른쪽 대각선 아래, 오른쪽, 아래의 값이 아니라 그 반대의 방향들로 값들을 변화시킨 것이었습니다.

 

탐색을 진행하며 우측 하단부의 값들은 좌측 상단부 값들의 영향을 받기 때문에 이렇게 한 것인데,

만약 반대 방향으로 진행하고 싶다면 (n,m)에서부터 진행을 해야합니다.

 

 

주의할 점

n = 1, m = 1이며 배열의 값이 0인 경우가 존재할 수 있기에,

가장 작은 정사각형의 길이를 0으로 설정하고 문제를 풀어나가야 한다는 점입니다.

 

 

 

 

전체 코드

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

int map[1005][1005];
int n, m;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char tmp;
            cin>>tmp;
            map[i][j] = tmp - '0';
        }
    }

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

    cout<<ans*ans;
    return 0;
}

 

점화식 하나 생각하는 것만으로 골드4의 난이도를 가진 문제인데, 그럴만하다고 여겨지는 점화식이었습니다...