Programmers > 연습문제 DP > #38 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

 

문제:https://programmers.co.kr/learn/courses/30/lessons/12905

 

 

 

 

1. 문제 설명

 

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

예를 들어

 

1 2 3 4

0 1 1 1

1 1 1 1

1 1 1 1

0 0 1 0

가 있다면 가장 큰 정사각형은

 

1 2 3 4

0 1 1 1

1 1 1 1

1 1 1 1

0 0 1 0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

 

2. 나의 코드

 

- 주어진 board보다 행과 열이 하나씩 큰 배열 d를 만든다.

- d를 0으로 초기화 시킨다.

- 배열 d는  board배열을 탐색하면서,  board의 해당 위치에서 만약 board의 값이 1이면 자신을 제외한 왼쪽 상단, 상단, 왼쪽 중 최솟값에 1을 더한 값을 더한다.

- 점화식 d[i][j] = Max(Max(d[i-1][j],d[i-1][j-1]),d[i][j-1])

- 원리는 자신을 제외한 주변의 최솟값(왼쪽 상단, 상단, 왼쪽)에 1을 더한다면, 해당 정사각형의 제곱근을 구할 수 있기 때문이다.

- 만약 하나라도 0이면 사각형이 성립되지 않으므로, 자기자신의 값인 1(최솟값(0) +1)이 저장된다.

- 만약 모두 1이면, 적어도 자신 주변에 있는 값(왼쪽 상단, 상단, 왼쪽)들은 모두 값을 가지기 때문에 2(최솟값(1)+1)가 저장된다.

- 만약 모두 2이상이면, 적어도 자신 주변에 있는 값(왼쪽 상단, 상단, 왼쪽)들은 모두 각각 길이가 2인 사각형에 속해 있기 때문에, 3이 저장된다.

- 방식은 딥러닝 CNN pooling 할때 봤던것 같다.

 

 

import java.util.Arrays;
import java.lang.Math;

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int [][] d = new int[board.length+1][board[0].length+1];
        
        for(int []row :d){
            Arrays.fill(row,0);
        }
        
        for(int i=1;i<d.length;i++){
            for(int j=1;j<d[i].length;j++){
                d[i][j] = board[i-1][j-1];
                if(d[i][j] == 1){
                    d[i][j] = Math.min(Math.min(d[i-1][j-1],d[i-1][j]),d[i][j-1])+1;
                }
            }
        }
        
        for(int k=1; k<d.length;k++){
            for(int h=1;h<d[k].length;h++){
                if(answer < d[k][h]){
                    answer = d[k][h];
                }
            }
        }
        answer*=answer;
        return answer;
    }
}