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

<링크>

 

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

프로그래머스

 

 

 

<문제>

• 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 
• 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
• 예를 들어

• 가 있다면 가장 큰 정사각형은

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

 

<제한사항>

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

 

<입력 및 출력>

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

 

<아이디어>

1. 가장 큰 정사각형은 모든 행과 모든 열이 1로 채워져있는 값!! -> 그러니 첫 행 or 첫 열에 1이 있는지 파악부터 하자.
2. 0행(0열) 부터 탐색을 시작할껀데.. 1인 녀석만 파악하면 돼! 조건문에 if == 1 걸면 되겠다.
3. 현재 좌표를 기준으로, 왼쪽, 위쪽, 왼쪽위쪽이 다 1이면 n에 +1을 해주면 되겠네..!! 그러면 길이가 1 더 늘어난거니까!
4. 정사각형의 넓이를 구하는 방법은 알죠? ㅎ

<풀이 - Java >

class Solution {
    public int solution(int [][] board) {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        int n = 0;
        int[][] dp = new int[row][col];

        // 일단 n이 젤길어야해. 행의 첫번째에 n의 값 (0 or 1)을 넣어주어요.
        for (int i = 0 ; i<row; i++){
            dp[i][0] = board[i][0];
            n = Math.max(n,dp[i][0]);
        }
        // 이하 동문
        for (int i = 0 ; i<col; i++){
            dp[0][i] = board[0][i];
            n = Math.max(n,dp[0][i]);
        }
        // 완탐 하면서...
        for (int i = 1 ; i<row; i++){
            for (int j = 1 ; j<col;j++){
                // 만약에 값이 1이면..
                if(board[i][j] == 1){
                    // dp[i][j] 전행, 전열, 왼쪽위에 0이 있는지 파악을 해요. 
                    // 만약에 다 1이면.. dp[i][j]의 길이는 2가 되겠군요.
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) +1;
                    n = Math.max(n, dp[i][j]);
                }
            }
        }
        answer = n * n;
        return answer;
    }
}