[프로그래머스_레벨2] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905#

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

처음에 for문으로 답을 찾으려 했다가 정확성은 맞았지만 효율성테스트에서 실패한 케이스다.

다시 문제를 분석하고 DP로 더 빠르게 풀 수 있는 것을 알게 된 뒤, 

재설계해서 풀었다.

 

먼저 DP배열에 모두 0을 넣고, board에 1이 담겨있는 곳의 dp값을 1로 초기화 해주었다.

만약 board값을 확인하는 과정에서 1이 발견되지 않으면 0을 반환하고 종료하도록 했다. 그렇지 않은 경우 최소 1의 넓이를 가질 것이므로 answer의 초기값은 1로 설정했다. (answer은 제일 큰 정사각형의 한 변의 길이의 의미임.)

 

그 후, dp를 돌면서 좌상, 좌, 상 부분의 dp값을 보고 제일 작은 요소를 찾아 +1한 것이 현재 위치에서 얻을 수 있는 가장 긴 정사각형의 한 변의 길이이므로 루프를 돌며 제일 긴 길이를 answer에 담아두었다.

 

루프를 다 돌고 나서는 길이를 저장해둔 answer의 제곱을 반환하도록 했다.

#include <iostream>
#include <vector>
using namespace std;
 
int solution(vector<vector<int> > board)
{
    int answer = 1;
    vector<vector<int> > dp;
    int row = board.size(), col = board[0].size();
    dp.assign(row, vector<int>(col, 0));
    bool no_one = true;
    for(int r=0; r<row; r++){
        for(int c=0; c<col; c++){
            if(board[r][c]) {
                dp[r][c] = 1;
                no_one = false;
            }
        }
    }   
    if(no_one) return 0;
    for(int r=1; r<row; r++){
        for(int c=1; c<col; c++){
            if(dp[r][c] == 1){
                dp[r][c] = min(dp[r-1][c], min(dp[r-1][c-1], dp[r][c-1])) + 1;
                answer = (answer >= dp[r][c]) ? answer : dp[r][c];
            }
        }
    }
    answer = answer * answer;
    return answer;
}