[프로그래머스] 가장 큰 정사각형 찾기 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

board[i][j]에 만들 수 있는 가장 큰 정사각형 크기를 저장하는 방식으로 풀어나간다.

 

예를 들어 2x2 크기의 board가 있다고 하자.

(1,1)의 위치에 만들 수 있는 가장 큰 정사각형의 변의 길이를 저장할 것이다.

이때, board[i][j]에 들어갈 값은 좌상단 대각선, 좌, 상단의 값중 제일 작은 값에 +1한 값이다.

 

3x3 board가 있다고 하자.

(2,2) 위치에서 좌상단 대각선, 좌, 상단 값중 작은 값에 +1을 한 값을 (2,2) 위치에 갱신시켜주면 된다.

왜냐하면, 좌상단 대각선에 들어 있는 값은

빨간색으로 칠해진 테투리 영역에서 가질 수 있는 최대 변의 길이이다.

좌, 우 각각 노란색, 초록색 테투리에서 가질 수 있는 정사각형 최대 변의 길이가 담겨져 있다.

굳이 3x3 배열을 모두 탐색하지 않아도 이 3가지 위치의 값으로만으로

(2,2) 위치에서 만들 수 있는 최대 정사각형의 크기를 알 수 있다.

 

단. 최대 정사각형 변의 길이를 구하는 위치의 값은 board[i][j] == 1 이여야 한다.

 

전체 코드

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

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(board[i][j]==1) {
                answer=max(answer, 1); // 1x1 정사각형이 있다면 정답은 최소 1이다.
                
                if(j-1>=0 && i-1>=0) { // 좌상단 대각선, 좌, 위로 이동이 가능하다면.
                    board[i][j] = min(board[i-1][j], board[i][j-1]);
                    board[i][j] = min(board[i][j], board[i-1][j-1]); // 3방향중 최소값 찾기.
                    board[i][j]+=1; // 최소값+1
                    answer=max(answer, board[i][j]*board[i][j]); // 넓이 갱신
                }
            }
        }
    }

    return answer;
}