15일만에 다시 백준 컴백, 첫 문제는 역시나 디피다.

문제

문제 링크

문제 접근

  • 이 문제는 1, 1에서 부터 우측 하단으로 원소를 하나씩 확인한다.
  • 해당 위치 값이 1이라면 위치의 좌, 상, 좌상 원소의 min값을 비교해주면서 해당 위치에서 만들 수 있는 정사각형 한변의 최대 길이를 저장해준다.
  • 이를 이용해서 최대 정사각형의 크기를 구한다.

주의할 점

  • 1, 1에서 부터 시작하기 때문에 0, 0만으로 이루어진 변의 길이가 1 짜리 사각형은 무시된다. 때문에 ans의 값은 arr[0][0]으로 설정해놓는다!

코드

#include <cstdio>
int n, m, x, ans, arr[1001][1001];
int d[3][2] = { {0, -1}, {-1, -1}, {-1, 0} };
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)scanf("%1d", &arr[i][j]);
    }
    ans = arr[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
            if(!arr[i][j])continue;
            int min = 987654321;
            for(int k = 0; k < 3; k++)if(min > arr[i + d[k][0]][j + d[k][1]])min = arr[i + d[k][0]][j + d[k][1]];
            arr[i][j] = min + 1;
            if(min + 1 > ans) ans = min + 1;
        }
    }
    printf("%d", ans*ans);
}

느낀점

  • 접근법이 안떠올라서 블로그를 참고했다. 아직 갈길이 멀다!