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

나는 첫번째로 이 문제를 dfs로 풀려고 했다.

board의 행과 열이 1000이하의 자연수 이므로 최대 시간 복잡도가 1000 ^ 4가 되므로 시간 초가가 될 거라는 것을

예상하고 풀었다...

당연히 시간 복잡도에서 실패,,,아래는 틀린 코드이다.

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

int n = 0;
int m = 0;

bool visit[1001][1001];

int rectangle(const vector<vector<int>>& board, int x, int y, int depth)
{    
    if(x + 1 >= m || y + 1 >= n)
    {
        return depth * depth;
    }
    
    if(board[y][x + 1] && board[y + 1][x] && board[y + 1][x + 1])
    {
         return min(rectangle(board, x + 1, y, depth + 1),
                    min(rectangle(board, x, y + 1, depth + 1), 
                        rectangle(board, x + 1, y + 1, depth + 1)));
    }else
    {
        return (depth) * (depth);
    }
    return 0;
}
int solution(vector<vector<int>> board)
{
    int answer = 0;
    m = board[0].size();
    n = board.size();
    
    for(int i = 0; i < board.size(); ++i)
    {
        for(int j = 0; j < board[i].size(); ++j)
        {
            if(board[i][j] == 1)
            {
                answer = max(answer, rectangle(board, j, i, 1));   
            }
        }   
    }
    return answer;
}

다른 사람 풀이를 보니, 보드에 사각형의 크기를 누적시키는 방법으로 풀었다.

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

(1, 1) 부터 순회하면서

좌, 상, 좌상의 값 중 최소값 + 1을 (1, 1)로 업데이트한다.

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

(1, 2) 의 경우에는

좌, 상, 좌상의 값 중 최소값 + 1을 (1, 2)를 2로 업데이트한다.

 

0	1	1	1
1	1	2	1
1	1	1	1
0	0	1	0

이런 식으로 순차적으로 순회하면

0	1	1	1
1	1	2	2
1	1	1	1
0	0	1	0

0	1	1	1
1	1	2	2
2	2	2	3
0	0	1	0

(2, 3)에 3이 나오게 되고, 최대값을 찾아가면 된다.

문제를 풀면서,,,board의 길이가 1인데 (0, 0) 값이 1인 경우와 0인 경우를 계산하는 것을 깜박했다...

기억하자...

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

int n = 0;
int m = 0;

bool visit[1001][1001];

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    m = board[0].size();
    n = board.size();
    
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j < m; ++j)
        {
            if(board[i][j] == 1)
            {
                board[i][j] = min(board[i - 1][j], min(board[i - 1][j - 1], board[i][j - 1])) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}