가장 큰 정사각형 찾기 (프로그래머스) - C++

• 문제
  • 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.
  • (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

• 설명
  • 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.

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

• 풀이
  • 표에서 1로 이루어진 가장 큰 정사각형을 찾아야한다.
  • 왼쪽 위에서부터 채워나가면서 가장 큰 정사각형을 찾는다.
  • 격자로 이루어진 맵에서 출발지에서 목적지까지 최단거리를 구하는 문제와 유사하다.
  • 하지만 이 문제는 왼쪽 위 대각선까지 포함하여, 왼쪽, 위, 대각선 3가지 방향을 고려해야한다. --> [i-1][j] , [i][j-1] ,[i-1][j-1]
  • 만약 해당 인덱스에 값이 1이라면 3가지 방향의 값 중 최솟값(가장 작은 정사각형의 크기) + 1 을 해준다. 
  • 만약 해당 인덱스에 값이 0이라면 그 인덱스에는 정사각형이 존재할 수 없으므로 그대로 0을 입력한다. (웅덩이와 같음)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int square_size(int left , int up , int cross)//세방향(왼쪽 위 대각선)의 값 중 가장 작은 값 + 1을 반환한다.
{
    return min(min(left,up),cross) +1;
}
 
int solution(vector<vector<int>> board)
{
    int answer = 0;
 
    
    for(int i = 0 ; i < board.size() ; i++)
    {
        for(int j = 0 ; j < board[i].size() ; j++)
        {
            if(i == 0 || j == 0)//가장자리는 1 또는 0 이므로 그 값 그대로 들어간다.
            {
                answer = max(answer , board[i][j]);
            }
            else// 가장자리가 아닌 곳들은 
            {
                if(board[i][j] == 1)//정사각형이 존재할 수 있다면(존재한다면)
                {
                    board[i][j] = square_size(board[i][j-1] , board[i-1][j] , board[i-1][j-1]);//해당 위치에 확장 가능한 최대한의 크기를 입력한다.
 
                    answer = max(answer , board[i][j]*board[i][j]);//최댓값을 갱신해준다.
 
                }
            }
            
            
        }
    }
    
    
    return answer;
}