프로그래머스_가장 큰 정사각형 찾기_Day22

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

프로그래머스

오늘은 프로그래머스 Level2로 분류된 문제를 풀어보았다. 2차원 배열의 크기가 최대 1000 x 1000으로 크지 않아 보이지만, 문제를 보자마자 직감적으로 브루트포스로 풀게 되면 효율성 채점에서 하나 정도는 틀리겠거니 싶었다. 

사실 이런 문제가 제일 어렵고 까다로운 것 같다. 정해진 공식이 있는 것도 아니고, 머리를 좀 굴려서 알고리즘을 효율적으로 최적화해야 하기 때문이다.

뭐 이렇게 생각하면 안 쉬운 문제가 없겠지만,, 안 돌아가는 머리를 부여잡고 오랜만에 머리를 좀 써보자. 

일단, 모든 배열의 원소가 0일 가능성도 있기 때문에 이 부분은 비즈니스 로직을 시작하기 전에 예외처리 해주어야 할 것 같다. 

문제에서 요구하는 정사각형의 넓이를 구하라는 말은 쉽게 보면 한 변의 길이의 최댓값을 구하라는 뜻이다. 
그렇다면 탐색을 아예 안 할 수는 없고, 각 지점에서 할 수 있는 최소한의 연산으로 탐색을 진행해야 한다. 

정사각형을 구성하는 가장 작은 단위는 1x1 사이즈의 한 지점이 될 것이다. 그러니 초기의 예외조건을 벗어난다면 한 변의 길이는 1로 초기화해서 시작하면 될 것이다. 

그다음으로 큰 크기가 2x2가 아닌가? 하여 특정 지점에서 8 방면을 탐색하는 것이 아니라, 상, 좌, 좌상 3 부분만 탐색하여 2x2단위로 정사각형이 이루어지는지 여부를 확인해 보면 될 것 같다. 
아래 그림처럼 한 지점에서 탐색하는 주변 정사각형의 범위를 최소로 잡는 것이다. 

그러기 위해선 배열의 인덱스는 1행 1열부터 시작해야 OutOfArrayIndexException이 발생하지 않을 것이다. 
0행 0열에서부터 시작하면 안되는가? 하고 생각할 수도 있어서 말하자면, 차이는 없을 것이다. 그저 배열의 끝 인덱스 조율을 위해 머리를 한 번 더 써야 할 뿐... 시도해 보고 더 편한 방법을 사용하길 바란다. 

1행 1열부터 탐색을 진행하 되, dp의 개념을 적용해서, 탐색하는 지점이 1이라면(0인 경우는 어차피 이전에 정사각형이 구성이 되었다고 하더라도, 0인 지점에서 리셋된 것이기 때문에 과감하게 스킵하자.), 해당 지점에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이를 저장한다.  
최솟값을 구했다면, 일단 해당 지점이 정사각형의 구성요소로 포함되었다는 뜻이기 때문에 +1을 해준다. 

쓰기 전에 어떻게 설명을 해야 하나 말로 하면 이해가 어려울 것 같은데 하는 걱정을 했는데, 역시 그런 듯하다. 

아래 그림을 통해 임의의 예시를 들어 설명해보겠다.

 왼쪽 그림이 입력으로 주어지는 board배열이라고 할 때, 하늘색으로 색칠된 영역이 탐색을 진행하는 영역이 되고, 
오른쪽 그림이 해당 지점에서 만들 수 있는 정사각형의 최대 크기를 dp형태로 채워나간 것이다. 

1행 1열 
-> 탐색 지점의 값이 1이라서 비교를 시작했는데, 0행 0열이 0이다. 그러면 일단 2x2크기의 정사각형을 만드는 것은 물 건너갔다고 보면 된다. 탐색 지점을 제외한 나머지 세 개지점의 값 중 가장 최솟값을 구해야 한다. 
그래야만 탐색 지점에 정사각형이 있을 때, 가장 큰 정사각형의 크기를 구할 수 있다. 
위의 그림에 경우에서는 가장 최솟값은 0이지만, 탐색지점에 있는 정사각형 만으로도 1x1의 정사각형을 구성할 수 있지 않나? 이를 위해 위에서 1을 더해야 한다고 한 것이다. 

1행 2열
-> 탐색 지점을 제외한 나머지 3개 지점 모두 정사각형이 존재한다. 이 경우 최솟값은 1이 될 것이다. 
이때, 탐색지점에 정사각형이 존재함으로써 성공적으로 2x2 정사각형을 만들 수 있다. 

이런 식으로 각 탐색지점을 탐색하면서 해당 지점에서 만들 수 있는 최대 길이 값을 저장하고, 전역 변수 answer에 대소 비교를 하여 최댓값을 저장할 수 있도록 한다. 

이 정도면 로직의 흐름을 얼추(?) 이해했으리라 믿는다.. 

아래 코드를 보면 좀 더 명확한 이해가 될 수도 있다.

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

        for(int i=1; i<board.length;i++){
            for(int j=1; j<board[0].length; j++) {
                if(board[i][j] == 0) continue; 
                board[i][j] = Math.min(Math.min(board[i-1][j], board[i][j-1]), board[i-1][j-1]) + 1;
                answer = Math.max(answer, board[i][j]);
            }
        }

        return answer*answer;
    }
    
    public boolean isAllZero(int [][] board) {
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(board[i][j] == 1) return false;
            }
        }
        return true;
    }
}