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

효율성테스트를 모두 실패한 모든 경우의 수를 찾기

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

vector<int> result(1001, 0);

void DFS(int x, int y, int size, vector<vector<int>> &board);

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int num = 0;
    for(int i = board.size(); i >= 1; i--)   //범위
    {
        if(i > board.size() || i > board[0].size()) continue;
        
        DFS(0, 0, i, board);
        
        if(result[i] == i * i) 
        {
            num = i;
            break;
        }
    }
    
    answer = result[num];
    
    return answer;
}

void DFS(int x, int y, int size, vector<vector<int>> &board)
{
    bool temp = false;
    
    if(result[size] == size * size) return;
    
    if(board[x][y] != 0)
    {
        for(int j = x; j < x + size; j++)    //x
        {
            for(int k = y; k < y + size; k++)
            {
                if(board[j][k] == 0)
                    temp = true;
            
                if(temp == true) break;
            }
        
            if(temp == true) break;
        }
    }
    else temp = true;
    
    if(temp == true)
    {
        if(x + 1 + size <= board.size())
            DFS(x + 1, y, size, board);
        
        if(y + 1 + size <= board[0].size())
            DFS(x, y + 1, size, board);
    }
    else
    {
        result[size] = size * size;
    }
}

 

효율성을 맞추기 위해서는 동적계획법을 이용하여 해결해야한다.

 

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

int solution(vector<vector<int>> board)
{
    int answer = 0;
    if(board[0].size() == 1)
    {
        for(int x = 0; x < board.size(); x++)   //x
        {
            if(board[x][0] == 1)
                return 1;
        }
    }
    else if(board.size() == 1)
    {
       for(int y = 0; y < board[0].size(); y++)   //y
        {
            if(board[0][y] == 1)
                return 1;
        }
    }
    else
    {
        for(int y = 0; y < board[0].size() - 1; y++)    //y
        {
            for(int x = 0; x < board.size() - 1; x++)   //x
            {
                if(board[x + 1][y + 1] == 0) continue;
                
                board[x + 1][y + 1] += min(min(board[x][y], board[x][y + 1]), board[x + 1][y]);
                answer = max(answer, board[x + 1][y + 1]);
            }
        }
    }
    
    
    return answer * answer;
}

 

풀이

1. 행이 하나일때와 열이 하나일 때의 경우를 따로 계산한다.
2. 그게 아닐 경우 이렇게 계산한다.

[x][y], [x][y + 1], [x + 1][y]를 비교해서 가장 작은 값을 [x + 1][y + 1]에 더해준다.

 

차근차근 x, y의 최대 길이까지 전진하면서 구하면 그것의 크기를 알 수 있는 원리이다.

 

하지만 

위 경우와 같이 [x + 1][y + 1]가 0일 경우는 사각형이 되지 않으므로 계산하지 않고 지나간다.

 

   3. 다 계산 후에 만약 answer가 0일경우는 최소 정사각형인 1x1이 있을 수도 있기 때문에 따로 계산한다.

   4. 그 경우도 없다면 answer * answer를 곱한 값이 최종 넓이이다.