문제

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를 반환해 주면 됩니다.

제한사항

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

접근1

Brute-force 식으로 접근해보았어요. 혹시나 했는데 역시나, 효율성 테스트에서 시간초과가 뜹니다. 1000 x 1000 배열에서 구성할 수 있는 정사각형이 없는 경우 $O(n^{3})$이 되니 어찌보면 당연한 결과겠지요.

답안

class Solution {
    public int solution(int [][]board){
        if(board.length <= 0)
            return 0;
        
        int rl = board.length;
        int cl = board[0].length;
        int offset = Math.max(rl, cl);
        for(int i = offset; i > 0; --i){
            for(int y = 0; y <= rl - i; ++y){
                for(int x = 0; x <= cl - i; ++x){
                    if(isValid(board, y, y + i, x, x + i))
                        return i * i;
                }
            }
        }

        return 0;
    }

    private boolean isValid(int[][] board, int y1 , int y2, int x1, int x2){
        for(int y = y1; y < y2; ++y){
            for(int x = x1; x < x2; ++x){
                if(board[y][x] == 0)
                    return false;
            }
        }
        return true;
    }
}

접근2

다른분의 풀이를 봤어요. 엄청나네요. Dynamic Programming 방식으로 접근을 하셨어요.

1. y=1 x=1부터 시작해요.
2. board[y][x]가 1일 경우, min{board[y-1][x], board[y][x-1], board[y-1][x-1]} + 1을 board[y][x]에 초기화해요.
3. board[y][x] 값이 answer보다 크면 초기화해요.
4. 2~3번을 board 길이까지 반복해요.

처음엔 와닿지 않았어요. 그런데 직접 그려보니 이해가 됐어요. 전개를 하다보면 board[y][x]에 초기화된 수치는 정확하게 해당 위치 기준으로 가장 큰 정사각형의 너비가 초기화되요.

1	2	3	4
0	1	1	1
1	min(1, 1, 0) + 1 = 1	min(1,1,1) + 1 = 2	min(1,1,2) + 1 = 2
1	min(1,1,1) + 1 = 2	min(2,1,2) + 1 = 2	min(2,2,2) + 1 = 3
0	0	min(2,0,2) + 1 = 1	0

예제에 해당 로직을 적용한 결과에요. 보시면 y, x를 기준으로 좌, 상으로 전개했을 경우 정사각혁의 최대 너비를 구할 수 있음을 확인하실 수 있어요.

푸신 분은 어떻게 이걸 바로 간파하셨던 걸까요. 아직도 벽이 느껴지네요 ㅎㅎ 쉽지 않지만 계속 분발해야겠어요 ㅠ.

답안

class Solution {
    public int solution(int [][]board){
        if(isAllZero(board))
            return 0;

        int answer = 1;
        for(int y = 1; y < board.length; ++y){
            for(int x = 1; x < board[y].length ; ++x){
                if(0 >= board[y][x])
                    continue;

                board[y][x] = Math.min(board[y - 1][x], Math.min(board[y][x - 1], board[y - 1][x - 1])) + 1;
                answer = Math.max(board[y][x], answer);
            }
        }
        
        return answer * answer;
    }
    
    private boolean isAllZero(int[][] board) {
        for(int y = 0; y < board.length; ++y){
            for(int x = 0; x < board[y].length; ++x){
                if(board[y][x] == 1)
                    return false;
            }
        }
        return true;
    }
}