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

문제

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

프로그래머스

 

---

 

문제 개요

주어진 2차원 배열 board에서 1과 0으로 이루어진 가장 큰 정사각형의 넓이를 계산하는 문제입니다.

 

접근 방법

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 효율적으로 해결할 수 있습니다.

 

1. DP 배열 초기화:

입력 배열과 같은 크기의 DP 배열을 생성합니다. DP 배열의 각 요소는 해당 위치에서 끝나는 가장 큰 정사각형의 한 변의 길이를 저장합니다.

2. 기본 조건 설정:

배열의 첫 번째 행과 첫 번째 열은 원본 배열의 값과 동일하게 설정합니다. 즉, board[i][j]가 1인 경우 dp[i][j]도 1로 설정합니다. 이는 가장자리에 있는 1은 그 자체로 정사각형의 한 변이 될 수 있기 때문입니다.

3. DP 배열 채우기:

2차원 배열을 순회하면서 각 요소가 1인 경우, 해당 위치에서 가능한 가장 큰 정사각형의 크기를 계산합니다.
이때, 현재 위치의 왼쪽, 위쪽, 대각선 위쪽의 값들을 참조하여, 이들 중 최소값에 1을 더한 값을 현재 DP 배열에 저장합니다. 이는 현재 위치에서 정사각형을 확장할 수 있는지를 판단하는 과정입니다.

 

4. 최대 정사각형 크기 추적:

DP 배열을 업데이트하면서 가장 큰 정사각형의 한 변의 길이를 추적합니다. 최종적으로 이 최대 길이를 제곱하여 넓이를 계산합니다.

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int[][] dp = new int[board.length][board[0].length];
        
        for(int i=0; i<dp.length; i++) {
            for(int j=0; j<dp[0].length; j++) {
                if(board[i][j] == 1) {
                    if(i==0 || j==0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    }
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }

        return answer*answer;
    }
}