[프로그래머스,Level 2] 가장 큰 정사각형 찾기 (JAVA 구현)

- 첫 풀이

  이 문제를 처음 풀 때는 board를 탐색하면서 1을 만나면 1부터 board의 길이만큼 증가시키며 정사각형을 만족하는지 판단하는 방식으로 진행하였는데, 몇몇 테스트 케이스는 통과하지만 이 경우는 모든 1에 대해서 수행하기 때문에 효율성 측면에서도 시간 초과가 발생한다. DFS나 BFS를 이용해 풀어볼까 했지만 불가능할 것 같아 다른 방법이 있나 찾아보게 되었다.

 

- 정답풀이

  결국 이 문제는 DP를 활용해야 한다. 자세한 설명은 다른 블로그를 참고하면 쉽게 알 수 있다.

class Solution
{
    public int solution(int [][]board)
    {
        // 1. DP 배열.
        int dp[][] = new int[board.length][board[0].length];
        int answer = Integer.MIN_VALUE;
        
        // 2. 행 또는 열의 길이가 1인 경우는 정사각형의 최대 크기는 1이다.
        if(board.length == 1 || board[0].length == 1) return 1;
        
        // 3. 0번 행, 열은 위와 같은 원리로 최대 크기는 1이므로 그대로 초기화.
        for(int i =0;i<board.length;i++)
            dp[i][0] = board[i][0];
        
        for(int i =0;i<board[0].length;i++)
            dp[0][i] = board[0][i];
        
        // 4. (1,1)부터 board 탐색.
        for(int i =1;i<board.length;i++){
            for(int j = 1;j<board[i].length;j++){
                // 5. 값이 1인 경우,
                if(board[i][j] == 1){
                    // 6. 좌상단, 좌, 상 중 최솟값 +1을 dp에 저장.
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                }
                // 7. dp에 저장되는 값 중 가장 큰 값이 최대 크기의 정사각형 한 변의 길이이다.
                answer = dp[i][j] > answer ? dp[i][j] : answer;
            }
        }    
        
        // 8. 정사각형 넓이 반환.
        return answer * answer;
    }
}