[2023년 11월 24일]가장 큰 정사각형(23분)

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

구현 아이디어 3분 구현 20분

풀이

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

// 푸는 법이 머리에 남아있어서 금방 품.
int check[1001][1001];
int dr[3] = {-1, -1, 0};
int dc[3] = {0, -1, -1};

int solution(vector<vector<int>> board)
{
    int answer = 1234;
    int mini = 2147000000;
    for(int i = 1; i < board.size(); ++i)
    {
        for(int j = 1; j < board[0].size(); ++j)
        {
            if(board[i][j] == 1)
            {
                mini = 2147000000;
                for(int k = 0; k < 3; ++k)
                {
                    int check_r = i + dr[k];
                    int check_c = j + dc[k];
                    if(board[check_r][check_c] < mini)
                        mini = board[check_r][check_c];
                }
                check[i][j] = mini + 1;
                board[i][j] = mini + 1;
            }
        }
    }
    
    if(mini == 2147000000)
    {
        printf("!");
        for(int j = 0; j < board[0].size(); ++j)
            if(board[0][j]) return 1;
        
        return 0;
    }

    int maxi = -2147000000;
    for(int i = 0; i < board.size(); ++i)
        for(int j = 0; j < board[0].size(); ++j)
        {
            if(maxi < check[i][j])
                maxi = check[i][j];
        }
    
    return answer = maxi * maxi;
}