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

https://programmers.co.kr/learn/courses/18/lessons/1879

알고리즘 문제 해설 - 가장 큰 정사각형 찾기 | 프로그래머스

처음에 문제를 읽고 생각한 풀이는

전체 배열을 돌면서 1을 만나면 dfs를 시작해서

오른쪽, 오른쪽 아래, 아래가 전부 1이면 정사각형이니까 재귀를 다시 돌리는 식으로

(chk배열로 방문 체크랑 범위 체크하면서)

전형적인 dfs문제처럼 풀려고 했는데

 

그런 방법을 구현하는데 메인함수에 for문이 무슨 5중까지 가고 알 수 없는 에러 터지고

아무리 생각해도 에바라 전부 없애고 다시 접근했다

아래는 망한 코드(미완성)

/*int dx[] = {1,0,1}; //오른쪽, 아래, 오른쪽아래
int dy[] = {0, -1,-1};
int chk[1000][1000];*/

/*int dfs(int y,int x, vector<vector<int>> board, vector<vector<int>>chk, int answer){
        if(board[y+dy[0]][x+dx[0]] == 1 &&
           board[y+dy[1]][x+dx[1]] == 1 &&
           board[y+dy[2]][x+dx[2]] == 1){
//           x+1<board.size() && y+1 < board[0].size()){
            dfs(y)
        }
    return answer;
}*/

/*int solution(vector<vector<int>> board) {
    int answer = 1;
    vector<vector<int>> chk(board.size(), vector<int>());
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board.size();j++){
            if(board[i][j] == 1){
//                int tmp = dfs(i,j,board,chk, answer);
                int tmp = 0;
                for(int k = 1;;k++){
                    for(int p=i;p<=i+k;p++){
                        for(int q=j;q<=j+k;q++){
                            if(board[p][q] != 1) goto out;
                            else tmp++;
                        }
                    }
                }
out:           
                if(tmp>answer) answer = tmp;
            }
        }
    }

    return answer;
}*/

 

접근을 좀 바꿔서 땅따먹기 문제처럼 푼다면 dp로 되지 않을까?

아까처럼 오른쪽으로 커지는거면 board크기가 유동적이지만 반대로 왼쪽/왼쪽위/위를 검사하면 지나간 곳은 무조건 정사각형이 됨

 

dp[i][j]는 i,j를 오른쪽 끝으로 하는 가장 큰 정사각형의 한 변의 길이를 담은 배열

현재가 1인데 왼쪽, 왼쪽위, 위가 전부 1이상이면 정사각형이고, 현재 위치를 셋 중에 최솟값+1(자기 자신의 길이)해서 넣어준다

최솟값을 선택하는 이유는 그림을 그려보면 알 수 있다

0 1 1

1 1 2

1 2 ?

이렇게 값이 있다고 할 때

2가 있는 두 곳은 2x2짜리 정사각형이 맞지만

맨 오른쪽 아래까지 포함해서 3x3짜리 정사각형은 아니다 왜냐면 왼쪽 위에 0이 있어서

 

초록색 2를 오른쪽 끝으로 하는 정사각형

빨간색 2를 오른쪽 끝으로 하는 정사각형

노란색 1을 오른쪽 끝으로 하는 정사각형(1x1)

이 셋을 포함하면서 현재 위치가 오른쪽 끝으로 하는 정사각형은

항상 셋 중 가장 작은 값+본인(1)이 된다

 

이걸 이중for문으로 계산하면서 가장 긴 변의 길이(=가장 큰 dp[i][j]값)를 따로 answer로 빼줌

맨 왼쪽 끝 줄, 맨 윗쪽 끝 줄은 어차피 정사각형이 되지 않으니까 넘기고 1부터 시작해도 됨

변의 길이를 구했으니까 정답은 제곱해서 넓이 리턴

 

여기까지 구현한 코드

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

int solution(vector<vector<int>> board) {
    int answer = 1;
    for(int i=1;i<board.size();i++){ //0번째 줄은 어차피 해당 없음, 만약 거기에 1이 있다고 해도 최대 1인 정사각형일 것이며
        for(int j=1;j<board[i].size();j++){ //그러면 answer기본값 1이 출력됨
            if(board[i][j] && 
               board[i][j-1] && board[i-1][j] && board[i-1][j-1]){ //지금 위치가 1이면서 왼쪽, 왼쪽위, 위가 1 이상이면
                board[i][j] = min(min(board[i][j-1],board[i-1][j]),board[i-1][j-1])+1; //셋 중에 최소값+1로 현재값을 해줌
                //왜냐면 가장 작은 길이가 정사각형이기 때문, +1은 본인 포함하면 변의 길이가 1 늘어나니까
                if(board[i][j]>answer) answer = board[i][j];
                //배열 전체 수 중에 가장 큰 값이 정답이다
            }
        }
    }
    int zero_chk = 0; //반례->배열에 0밖에 없을 경우 answer은 0이다
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            zero_chk+=board[i][j];
        }
    }
    if(zero_chk == 0) return 0;
    return answer*answer;
}

하지만!! 여기까지만 하면 틀렸다고 나옴

반례가 있기 때문 만약 배열에 1이 없고 0만 있다면?

0만 있으면 정사각형 넓이도 0이니까 따로 체크해줘야 함

나는 board값을 다 더해서 0이면 0리턴하게 따로 빼줌