[ 프로그래머스 lv2 ] 가장 큰 정사각형 찾기 (c++)

문제

---

 

 

 

 

 

 

풀이

---

 

처음에는 그래프나 탐색형 문제로 생각했다. 그러나 이것은 방법도 난해했고, 시간 복잡도도 기본적으로 벡터 최대 크기가 1000 * 1000 인데, 그 안에서 또 정사각형인지 체크하는 방식도 최대 1000 * 1000 만큼 걸릴 수 있기에, 1000 * 1000 * 1000 * 1000으로 시간초과가 난다는 점이 문제였다.

 

 

이 문제는 dp 문제였다. 정사각형을 탐색할 때 나는 board에서 1을 찾으면 왼쪽 위의 1로 생각해서 밑으로 내려갈 생각을 했는데, 1을 왼쪽 위가 아닌 오른쪽 아래로 두고 계산을 하는 것이 방법이였다.

 

 

 

왜 dp 인가??

 

 

그림을 그려서 확인해보면, (3, 2)의 1을 오른쪽 밑 꼭짓점으로 두는 정사각형 중 가장 큰 정사각형을 찾으려면, board[2 - 1][3], board[2][3 - 1], board[2 - 1][3 - 1] 을 확인해봐야한다. (각 각 빨강, 파랑, 초록으로 동그라미 친 부분이다.)  만약 저 중 0이 있다면, 정사각형이 되지 못하니 (3, 2)에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 1이 끝이다. (자기 자신)

 

 

만약 2 x 2 정사각형인지 확인했다면, 그 다음 3 x 3 정사각형이 가능한지 확인해야한다. 그럼 저렇게 색으로 칠한 사각형들이 모여 체크되는 것으로 생각할 수 있다. 

 

 

그럼 문제가 쪼개진다. 3 x 3 부분이 정사각형인지 알려면, 2 x 2 정사각형 3개가 체크되면 되는 것이다. 

 

 

이걸 점화식으로 나타내보자.

 

 

board[i][j] = min(board[i - 1][j], board[i][j - 1]), board[i - 1][j - 1])

 

 

3 부분중 가장 작은 값을 찾는 이유는 0이 포함된 곳이 있다면 정사각형이 되지 않기에, 0이 있는 작은 정사각형 부분을 찾는 것이다. 0이 포함되어 있었다면 값이 다른 색의 사각형에 비해 작을테니 말이다. 

 

 

ex) 만약 위 그림에서 초록색 사각형 부분 어딘가에 0이 있다면, 초록색으로 동그라미 친 부분이 1이 아니라 0일 것이다. (이는 위에서 설명했으니 알 것이다. )  그러면 (3, 2) 입장에서 그릴 수 있는 최대 크기의 정사각형은 3 x 3은 안 되니, 2 x 2인 2가 되어야한다. 

 

 

 

 

#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[0].size(); j++){
            if(board[i][j]){
                board[i][j] = 1 + min(min(board[i - 1][j], board[i][j - 1]), board[i - 1][j - 1]);
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}

 

 

문제 아이디어를 떠올리는 게 정말 쉽지 않았다. 역시 dp문제는 많이 풀어야겠다.