[프로그래머스] 가장 큰 정사각형 찾기 / C++

문제 설명

1과 0으로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

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

가 있다면 가장 큰 정사각형은

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

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

제한 조건

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int x, y, tmp;
    int row = board.size();
    int col = board[0].size();
    int square[row][col];
    
    for (y = 0; y < row; y++)
    {
        square[y][0] = board[y][0];
        answer = max(answer, square[y][0]);
    }
    for (x = 0; x < col; x++)
    {
        square[0][x] = board[0][x];
        answer = max(answer, square[0][x]);
    }
    for (y = 1; y < row; y++)
    {
        for (x = 1; x < col; x++)
        {
            if (!board[y][x])
            {
                square[y][x] = 0;
                continue;
            }
            tmp = min(square[y - 1][x], min(square[y - 1][x - 1], square[y][x - 1]));
            square[y][x] = tmp + 1;
            answer = max(answer, square[y][x]);
        }
    }
    return answer * answer;
}

 

square는 해당하는 1 X 1 정사각형이 속한 가장 큰 정사각형의 한 변의 길이를 저장한다. square[y][x]를 기준으로 square[y - 1][x], square[y - 1][x - 1], square[y][x - 1]의 값을 확인하여 (가장 작은 값 + 1)을 하면 square[y][x]가 속한 정사각형의 한 변의 길이가 된다.

예를 들어 다음과 같은 board가 주어진다고 하자.

[board]

0	0	1	1
1	1	1	1

첫 번째 행과 첫 번째 열은 비교할 수 있는 값이 부족하기 때문에 자기 자신의 값을 square에 그대로 저장한다. 즉, 0이면 정사각형에 포함되지 않으므로 0을 저장하고, 1이면 자기 자신으로만 이루어진 정사각형에 포함되므로 1을 저장한다.

이후, (1, 1)부터 (row, col)까지의 값을 확인한다. board[y][x]가 0이라면 정사각형에 포함되지 않으므로 0을 저장하고 다음으로 넘어간다. board[y][x]가 1이라면 왼쪽, 위쪽, 왼쪽 대각선 위쪽의 square값 중 가장 작은 값에 1을 더한 결과를 저장한다. 이때, 가장 큰 정사각형의 한 변의 길이를 저장하는 answer를 갱신한다.

[square]

0	0	1	1
1	1	1	2

최종적으로 answer는 2가 되고, 가장 큰 정사각형의 넓이를 구해야 하므로 answer * answer를 return하면 된다.

 

링크

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

github.com/inbdni/Programmers/blob/master/level02/%EA%B0%80%EC%9E%A5%ED%81%B0%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95%EC%B0%BE%EA%B8%B0.cpp

inbdni/Programmers