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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

2차원 배열이 들아온다고해서 2x2 사이즈 이상이라고 생각했다가 테스트케이스 1번이 계속 틀려서 한참을 헤맸다... [[1]] 인 경우가 있을 수 있다는 것을 간과하였다..

풀이

동적계획법으로 해결할 수 있다.
board[i-1][j], board[i][j-1], board[i-1][j-1] 중 최소값에 1을 더해준 수를 board[i][j]에 대입해주면서 board를 갱신하여 해결하였다.

예를 보면서 확인해보자

(1, 1) 위치에서 탐색을 시작한다.

(0, 0), (0, 1), (1, 0)의 값 중 최소값이 0이므로 (1, 1)의 위치를 1로 갱신한다.

(0, 1), (0, 2), (1, 1) 이 모두 1이므로 (2, 1)은 2로 갱신한다. 2로 갱신되었다는 의미는 2x2의 정사각형을 만들 수 있다는 의미이다.

(2, 0), (3, 0), (2, 1) 중에 최소값이 1이므로 (3, 1)은 2로 갱신한다. 

이러한 방식으로 모든 칸을 갱신하면 위의 그림이 되고 3x3이 가장 큰 정사각형이라는 것을 알 수 있다.

코드

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

int solution(vector<vector<int>> board)
{
    // 사이즈가 1x1이면서 board[0][0]가 1인 경우 예외처리
    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] == 0) continue;
            else{
                int tmp = min(min(board[i-1][j], board[i][j-1]), board[i-1][j-1]) + 1;
                board[i][j] = tmp;
                answer = max(answer, tmp);
            }
        }
    }
    return answer * answer;
}