[Java] 가장 큰 정사각형 찾기

문제

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

 

예를 들어

위와 같은 표가 있다면 가장 큰 정사각형은

위와 같이 2, 3, 4에 있는 크기가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

 

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

class Solution {
    public int solution(int [][]board) {
        int answer = 0;
        
        if(board.length == 1 || board[0].length == 1) { return 1; }
        
        for(int x = 1; x < board.length; x++) {
            for(int y = 1; y < board[0].length; y++) {
                if(board[x][y] == 0) { continue; }
                int left = board[x][y-1];
                int up = board[x-1][y];
                int leftUp = board[x-1][y-1];
                
                board[x][y] = Math.min(left, Math.min(up, leftUp)) + 1;
                answer = Math.max(answer, board[x][y]);
            }
        }

        return answer*answer;
    }
}

 

처음에는 그래프 문제인가 싶어서 한참을 들여다보다가 그래프로는 정사각형을 찾을 수 없다는 것을 알게 되었다.

결국 DP(Dynamic Programming)로 해결해야 한다는 힌트를 보고 깨달았다.

 

방법은 간단한데, (1, 1)부터 시작을 해서 해당 칸을 기준으로 좌측, 상단, 좌측상단 세 가지 좌표값을 확인한다. 만약 셋 다 1이라면 정사각형을 만들 수 있다는 뜻이므로 기준이 되었던 칸을 2로 만들어준다. 기준이 된 칸에다가 해당 정사각형의 넒이를 저장하는 것이다. 그렇게 다음 칸으로 이동을 한다.

 

단, 값을 저장할 때, 좌측, 상단, 좌측상단 세 값중 최소값의+1을 해줘야하는데,

만약 기준이 되는 칸 (x, y)에서 좌측(x, y-1), 상단(x-1, y), 좌측상단(x-1, y-1)을 봤을 때, 좌측상단(x-1, y-1) 만 2 이고 나머지는 1이라면, 이는 정사각형이 제대로 뻗어나가지 못한(?) 것이다.

사실 그림을 그려서 (1, 1) 부터 시작을 해서 하나씩 그려나가다보면 이해하기 쉽다.

 

 

출처

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