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

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기 문제는 동적 프로그래밍(DP)을 활용하여 문제를 풀 수 있습니다.

동적 프로그래밍은 어려운 문제를 여러 개의 하위 문제로 쪼갠 후, 이 하위 문제들을 먼저 해결하여서 더 큰 문제를 푸는 방법입니다.

가장 큰 정사각형을 찾는 문제를 하위 문제로 쪼갠다면 가장 작은 정사각형을 찾음으로써 가장 큰 정사각형을 찾으면 되겠죠..

문제 풀이 방식

1. 작은 정사각형을 찾기 위해 자신을 기준으로 왼쪽, 왼쪽 상단, 상단의 3방향의 숫자를 보고 가장 작은 정사각형을 판단합니다.

2.  가장 작은 정사각형을 찾았다면 자기 자신의 값에 +1을 한다. 주변 모두가 1이라면 2를 저장해주면 된다.

3. 만약 자기 주변의 방향이 모두 2를 가리킨다면 2의 크기를 가진 정사각형이 자기 주변에 모여 있는 것이므로 자신을 포함한다면 3의 길이를 가진 정사각형이 된다.

4. 이런 식으로 계속해서 작은 정사각형의 합을 더해간다면 가장 큰 정사각형을 찾을 수 있다.

문제 풀이 코드

class Solution
    {
        public int solution(int [][]board)
        {
            if(zeroFind(board) == 0)
                return 0;
            return findSquare(board);
        }

        private int zeroFind(int[][] board){

            for(int r=0; r<board.length; r++){
                for(int c=0; c<board[r].length; c++){
                    if(board[r][c] != 0)
                        return 1;
                }
            }
            return 0;
        }

        private int findSquare(int[][] board) {
            int max = 1;
            for(int r=1; r<board.length; r++){
                for(int c=1; c<board[r].length; c++){
                    if(board[r][c] > 0) {
                        int min = Math.min(board[r][c-1], board[r-1][c]);
                        min = Math.min(min, board[r-1][c-1]);
                        board[r][c] = min + 1;
                        if(board[r][c] > max)
                            max = board[r][c];
                    }
                }
            }
            return max*max;
        }
    }

처음에는 zeroFind()라는 매서드를 작성하지 않아서 테스트 케이스 8번이 계속 실패했습니다. 혹시 배열의 값이 모두 0인 경우가 있지 않을까 싶어 작성해서 정답을 제출하니 모든 테스트 케이스를 통과할 수 있었습니다.