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

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12905

문제 난이도

Lv2

문제 접근법

정사각형을 구하는 문제이기 때문에 1x1 (1칸 값)을 제외하고 가장 작은 정사각형은 2x2이다.
이를 이용해 점화식을 세우고 구하는 DP 문제다.

사각형 맨 끝을 중심(board[i][j])으로 두고, board[i-1][j], board[i][j-1], board[i][j] 사이에서 최소값을 구해 +1을 하면 된다.

추가한 알고리즘
algorithm

통과 코드

#include <iostream>
#include<vector>
#include <algorithm>

using namespace std;


int solution(vector<vector<int>> board)
{
    int answer = 0;
    int row = board.size();
    int col = board[0].size();
    if(board[0][0] == 1 && (row <= 1 || col <= 1)) return 1;
    
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            int up = i-1;
            int left = j-1;
            if(up <0 || up >=row || left <0 || left >=col || board[i][j] <1 ) continue;
            int minV = min(board[up][j], min(board[i][left], board[up][left]));
            board[i][j] = minV+1;
            if(answer < board[i][j]) answer = board[i][j];
        }
    }
    
    return answer * answer;
}

피드백

시도 1.
처음에 answer = -1를 두고 제출했는데 테스트 케이스 8번이 틀렸다 -> 온통 값이 0일 경우가 있어 -1 * -1은 1이므로 답이 되지 않아서 틀린거다.

시도 2.
answer = 0으로 두고 제출하니깐 테케 1 번에서 틀렸다. 사이즈가 1이고 그 한칸이 1이라면 가장 작은 사각형은 1이니깐 0하고 답이 틀리다. 그래서 중간에 if(board[0][0] == 1 && (row <= 1 || col <= 1)) return 1;을 넣어 통과시켰다.