백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)

아이디어

• 그래프 순회하면서 대각선만 DFS로 가면 안될까?
  • 노드 개수 : O(N^2)
  • 각 노드에서 순회해야할 갯수, 대각선만 보면 됨, O(N)
  • O(N^3) = 1e9 > 시간초과
• 이전에 구한 정사각형을 다음에 활용 가능? > DP 사용
  • DP[j][i] = j, i칸에서 가장 큰 정사각형의 크기
  • 해당 노드가 0일경우 넘어감
  • 해당 노드가 1일경우, 왼쪽, 왼쪽위 대각선, 위쪽 중 가장 작은값에 1 더한 값으로 갱신

시간복잡도 계산

• O(N^2) 순회
• 각 노드에서 3개 지점만 확인
  • 시간복잡도 : O(3*N^2) = 3e6

인트 계산

• 정사각형 크기 : 최대 1e6 > INT 사용 가능

코드

#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1010][1010];
int map[1010][1010];
int main() {
    //dp 초기화
    fill(&dp[0][0], &dp[1009][1010], 0);
    
    int N,M; cin >> N >> M;
    for(int j=0; j<N; j++) {
        string s; cin >> s;
        for(int i=0; i<M; i++) {
            map[j][i] = s[i]-'0';
        }
    }
    
    int maxv = 0;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(j==0 || i==0) dp[j][i] = map[j][i];
            else if(map[j][i] == 1){
                // 3방향중 가장 작은 값에다 1더한값으로 갱신
                dp[j][i] = min(min(dp[j-1][i], dp[j-1][i-1]), dp[j][i-1]) + 1;
            }
            maxv = max(maxv, dp[j][i]);
        }
    }
    
    cout << maxv*maxv << '\n';
    return 0;
}
 

문제유형

• DP - 2차원 배열
  • 단순히 모양이 2차원일뿐, 1차원 DP와 같이 앞의 값을 활용해 풀면 됨

비슷한 문제

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