[Level 2] 2. 가장 큰 정사각형 찾기

2. 가장 큰 정사각형 찾기

Algorithm - Level 2

- 풀이

+ 다중 중첩 for 문을 이용한 풀이

int solution(vector<vector<int>> board)
{
    int answer;
    int max = board.size()==board[0].size() ? board.size() : min(board.size(), board[0].size());
    
    int hi=-1, hj=-1;
 
    while(1){
        for(int a=0; a+(max-1)<board.size(); a++){
            for(int b=0; b+(max-1)<board[a].size(); b++){
                if(hi>=a && hi<=a+(max-1))
                    if(hj>=b && hj <= b+(max-1))
                        continue;
                for(int i=a; i<a+max; i++){
                    for(int j=b; j<b+max; j++){
                        if(board[i].at(j)==0){
                            hi = i; hj = j;
                            goto next;
                        }
                    }
                }
                return max*max;
                next:;
            }
        }
        if(--max == 0){
            return 0;
        }
    }
}

위 풀이 방법은 현재 입력으로부터 가질 수 있는 가장 큰 정사각형이 몇인가를 판단하는 방법이다.

즉, 4x4입력이 들어오면 가장 큰 정사각형은 입력과 같은 4x4로 하나의 원소라도 0을 가진다면 만족하지 못하기 때문에 4x4보다 작은 3x3 으로 줄이며 3x3이 되었을 경우, 1칸씩 위, 아래로 움직여 다시 판단한다.

당연하듯이 다중 for문을 사용하면 시간이 많이 소요된다.

-> 효율성 테스트에서 실패

시간 소요를 최소화로 하고자 continue, goto문을 사용하였지만 3개의 효율성 테스트 중 1개만 통과.

+ Dynamic Programming, 점화식을 이용한 방법

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

적분영상을 구하는 방법과 유사한 방법으로 0행, 0열에 존재하는 원소는 제외하며 위에서 아래로, 왼쪽에서 오른쪽으로 진행하여 현재 원소가 1이면 현재 원소에서 위, 위에서 왼쪽, 왼쪽에 존재하는 원소 중 최소값에 1을 더하여 해당 위치에 저장하고 다음에 이를 이용하는 방법이다.

정사각형의 크기는 이 원소값 중 최대값에 1을 더한 것의 제곱과 같다.

단 위 방법은 0행과 0열에 존재하는 원소는 참조만하기 때문에 만약 1행 1열부터 뒤로 존재하는 모든 원소가 0일 경우, 0행이나 0열에 존재하는 원소가 하나라도 1이 있으면 정사각형의 크기는 1이 되기 때문에 위 방법에 들어가기전 0행, 0열에 1이 존재하는지를 파악하고 넘어가야한다.