문제

O와 X로 채워진 표가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 O로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 findLargestSquare 함수를 완성하세요. 예를 들어

1 2 3 4 5
X O O O X
X O O O O
X X O O O
X X O O O
X X X X X

가 있다면 정답은

1 2 3 4 5
X O O O X
X O O O O
X X O O O
X X O O O
X X X X X

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

풀이 1

class TryHelloWorld
{
    public int findLargestSquare(char [][]board)
    {
        int answer = 0;
        int [][]arr = new int[board.length][board[0].length];

        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j]=='O'){
                	arr[i][j] = 1;
                }else{
                	arr[i][j] = 0;
                }
            }
        }

        for(int i=1;i<arr.length;i++) {
            for(int j=1;j<arr[i].length;j++) {
                if( arr[i][j] == 1 ) {
                    int minVal = 0;
                    minVal = arr[i-1][j] < arr[i][j-1] ? arr[i-1][j] : arr[i][j-1];
                    minVal = arr[i-1][j-1] < minVal ? arr[i-1][j-1] : minVal;

                    arr[i][j] = minVal + 1;
                    answer = answer < arr[i][j] ? arr[i][j] : answer;
                }
            }
        }

        return answer*answer;
    }
    public static void main(String[] args)
    {
        TryHelloWorld test = new TryHelloWorld();
        char [][]board ={
        {'X','O','O','O','X'},
        {'X','O','O','O','O'},
        {'X','X','O','O','O'},
        {'X','X','O','O','O'},
        {'X','X','X','X','X'}};

        System.out.println(test.findLargestSquare(board));
    }
}

슬슬 밑천이 드러나고 있다. 이제까진 어떻게든 풀 수 있었는데 이건 봐도 어떻게 풀 지 감이 안 잡혀서 고민하다 풀이를 보았다. 살펴보니 DP, 동적 프로그래밍(Dynamic Programing)이라는 개념이 쓰이더라.

큰 문제를 작은 문제로 나누어 조금씩 확장시켜 해결나가는? 알고리즘 풀 때 중요한 개념이자 풀이법이라고 한다.

풀이를 살펴보면 먼저 주어진 X,O 배열을 계산하기 쉽게 1과 0으로 이루어진 배열로 다시 만들어준다. 그리고나서 새로 만든 배열을 탐색해나가는데 (1,1) 부터 탐색을 한다. 값을 비교할 때 선택된 배열값의 좌측, 좌측상단, 상단의 값과 비교하기 때문에 (1,1) 부터 탐색을 하는 것이다.

배열 크기만큼 다 돌리면 제일 큰 값이 answer에 저장되는데 해당 값을 제곱하게 되면 가장 큰 정사각형의 크기가 나오게 된다.