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

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

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

 

DP를 이용하여 푸는 문제, 정사각형 오른쪽 아래 점이 1이고, 그 점을 기준으로, 왼쪽, 위쪽, 왼쪽 가운데 점의 값이 1 이상이면 길이가 2이상인 정사각형 조건 성립

1. 처음 위치는 (1,1)에서 시작
2. 탐색 하는 점 위치를 기준으로 왼쪽, 위쪽, 왼쪽 대각선의 값 중 최소값에서 +1 (누적하며 계속해서 오른쪽 아래의 점을 갱신)
3. 최대값 = 가장 큰 정사각형의 넓이의 한 변

 

#include <iostream>
#include<vector>
using namespace std;
int solution(vector<vector<int>> board) {
    int answer = board[0][0]; // 한개 입력 받았을 때를 위한 초기화 값
    
    for(int i = 1; i < board.size(); i++) {
        for(int j = 1; j < board[i].size(); j++) {
            if(board[i][j] == 1) {
                board[i][j] = min(board[i][j-1], board[i-1][j]); // 먼저 왼쪽, 위 중 최소값 구한 후
                board[i][j] = min(board[i][j], board[i-1][j-1]) + 1; // 왼쪽 대각선 최소값을 구한다 그 후 +1
                answer = max(board[i][j], answer);
            } 
        }
    }
    
    return answer * answer;
}