★[200706] 가장 큰 정사각형 찾기 - 연습문제(level2)

이 문제는 기말고사 이전에 풀었던 문제지만 그 때 정리를 하지 못해서 뒤늦게 정리해본다.

programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

1. 문제 이해

- 0과 1로 이루어진 직사각형 표(2차원 배열 board로 주어짐)

- 1로 이루어진 가장 큰 정사각형 찾아 넓이를 return!!

 

2. 전략

Dynamic Programming(동적계획법) : 이전 단계의 최대값(최적의 답)을 다음 단계에서 활용

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

- board[0, 0]부터 시작해서 행우선으로 탐색

- i와 j가 1이상이고 만약 board[i, j] 값이 1이라면...

      board[i, j] 값 = board[i-1, j], board[i, j-1], board[i-1, j-1]의 값 중 최소값 + 1 [단, 최소값이 0보다 클 때]

→ 만들 수 있는 정사각형의 최대값(max)을 갱신!!(아래 그림 참고)

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

- max * max를 return!!

 

3. 참고사항

- 이전 풀이 : getMaxRec 함수를 이용

board[x, y]를 시작점(가장 왼쪽 끝)으로 한 정사각형의 변 길이를 size(초기값 1)로 하여 계산

이 중에서 max값을 return

→ (문제점) 시간이 너무 오래걸려 효율성의 문제 발생!!

- 시작점이 아닌 끝점으로 지정하여 이전 계산 결과를 이용할 수 있는 발상이 필요!!!

 

4. 코드

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int row = board.length;
        int column = board[0].length;
        int sx = 0, sy =0;
        int max = 0;
        if(board[0][0] == 1)    max=1;
        for(int i = 1; i < row; i++){
            for(int j =1;j< column; j++){
                /*if(board[i][j] == 1){
                    sx = i; sy = j;
                    max = Math.max(max, getMaxRec(sx,sy,board,row,column));
                }*///효율성 문제 발생
                if(board[i][j] == 1){
                    int min = Math.min(board[i-1][j], Math.min(board[i][j-1], board[i-1][j-1]));
                    if(min > 0) board[i][j] = min+1;
                    max = Math.max(max, board[i][j]);
                }
            }
        }
        answer = max*max;
        return answer;
    }
    
    //효율성 떨어지는 함수 getMaxRec
    public int getMaxRec(int x, int y, int[][] board, int row, int column, int max){
        int size = 1; //실제 길이는 2
        boolean check = true;
        while(x+size < row && y+size < column){
            for(int i = x; i < x+size; i++){
                if(board[i][y+size] != 1){
                    check = false; break;
                }
            }
            for(int i = y; i < y+size; i++){
                if(board[x+size][i] != 1){
                    check = false; break;
                }
            }
            if(board[x+size][y+size] !=1)   check=false;
            if(check)   size++;
            else    break;
        }
        return size;
    }
}