Programmers | Level 2 | 가장 큰 정사각형 찾기

Programmers | Level 2 | 가장 큰 정사각형 찾기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Dynamic Programming

󰧭 Description

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

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

1	2	3	4
0	*	*	*
1	*	*	*
1	*	*	*
0	0	1	0

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

 Constraints

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

󰦕 Examples

board	result
[[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

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(int [][]board) {
        int rows = board.length;
        int cols = board[0].length;
        int max = 0;  // 최대 정사각형 변의 길이 저장

        int[][] dp = new int[rows][cols];  // dp 배열 선언

        // 첫 번째 행과 첫 번째 열 초기화
        for (int i = 0; i < rows; i++) {
            dp[i][0] = board[i][0];
            max = Math.max(max, dp[i][0]);  // 첫 열에서 최대값 갱신
        }
        for (int j = 0; j < cols; j++) {
            dp[0][j] = board[0][j];
            max = Math.max(max, dp[0][j]);  // 첫 행에서 최대값 갱신
        }

        // 나머지 부분에 대해 dp 테이블 업데이트
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (board[i][j] == 1) {
                    // 현재 위치가 1일 때, 좌, 상, 좌상 대각선 값 중 최소값 + 1
                    dp[i][j] = minimum(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);  // 최대 정사각형 변의 길이 갱신
                }
            }    
        }

        return max * max;  // 가장 큰 정사각형의 넓이를 반환
    }

    // 주어진 값들 중 최소값을 구하는 함수
    private int minimum(int... numbers) {
        int min = Integer.MAX_VALUE;
        for (int number : numbers) {
            if (number < min) min = number;
        }
        return min;
    }
}

 Approaches

이 문제는 Dynamic Programming(동적 계획법)을 이용하여 해결할 수 있습니다. 주어진 배열에서 1로 이루어진 가장 큰 정사각형을 찾는 문제이며, 각 위치에서 정사각형을 확장하는 방식으로 최대 넓이를 계산합니다.

1. 문제 분석

이 문제는 2차원 배열에서 1로 이루어진 가장 큰 정사각형을 찾아 그 넓이를 구하는 문제입니다. 배열 내에서 1이 인접한 위치들에서 정사각형을 형성할 수 있으며, 이를 확장해 나가면서 가장 큰 정사각형을 찾아야 합니다. 이를 위해 Dynamic Programming을 사용하여, 각 위치에서 만들 수 있는 가장 큰 정사각형의 크기를 기록하는 방식으로 문제를 해결합니다.

이 문제에서 DP 테이블은, 각 위치에서 만들 수 있는 최대 정사각형의 변의 길이를 저장하는 배열입니다. DP 테이블의 각 칸은 그 위치를 오른쪽 아래로 하는 가장 큰 정사각형의 변의 길이를 의미합니다. 이를 구하기 위해서는 해당 위치의 왼쪽, 위쪽, 대각선 위쪽 칸을 참고하게 되는데, 그 이유는 정사각형을 확장할 수 있는지 여부가 이 세 방향의 값에 의해 결정되기 때문입니다.

구체적으로, 어떤 위치에서 1로 이루어진 정사각형을 만들려면, 그 왼쪽, 위쪽, 대각선 위쪽 위치에도 정사각형을 만들 수 있어야 합니다. 그렇기 때문에, 현재 위치에서 만들 수 있는 최대 정사각형의 변의 길이는 왼쪽, 위쪽, 대각선 위쪽의 값 중 가장 작은 값에 1을 더한 값이 됩니다. 이 세 방향 중 하나라도 1로 이루어진 정사각형을 만들 수 없다면, 그 위치에서는 더 큰 정사각형을 만들 수 없기 때문에 최소값을 선택하여 확장을 결정합니다.

배열에서 가장 큰 정사각형을 찾는 과정을 설명하기 위해 DP 테이블을 사용합니다. 예를 들어, 다음과 같은 배열이 있다고 가정해 보겠습니다.

1 1 1 0
1 1 1 1
1 1 1 1
0 1 1 1

처음에는 이 배열에서 1이 있는 위치를 기준으로 가능한 정사각형을 확장해 나가야 합니다. 이를 위해 각 위치에서 만들 수 있는 가장 큰 정사각형의 크기를 기록하는 dp 테이블을 사용합니다. 이 테이블은 원래 배열과 같은 크기로 초기화되고, 첫 번째 행과 열은 그대로 복사됩니다. 예를 들어, 위 배열의 첫 번째 행과 열은 변환 후에도 그대로 유지됩니다.

1 1 1 0
1 . . .
1 . . .
0 . . .

이후 각 칸에서 정사각형을 확장할 수 있는지 판단합니다. 현재 위치에서 1이 있을 경우, 해당 위치의 왼쪽, 위쪽, 왼쪽 위 값 중 최소값을 찾아 그 값에 1을 더합니다. 예를 들어, (1,1) 위치에서 왼쪽(1), 위쪽(1), 왼쪽 위(1) 중 최소값을 찾아 1을 더하면 2가 됩니다. 따라서, (1,1) 위치에서 만들 수 있는 가장 큰 정사각형의 크기는 2x2입니다.

1 1 1 0
1 2 . .
1 . . .
0 . . .

마찬가지로 (1,2) 위치에서도 왼쪽(2), 위쪽(1), 왼쪽 위(1) 중 최소값에 1을 더하면 2가 됩니다. 이를 반복하면 다음과 같이 테이블이 채워집니다.

1 1 1 0
1 2 2 .
1 . . .
0 . . .

(2,2) 위치에서는 왼쪽(2), 위쪽(2), 왼쪽 위(2) 중 최소값에 1을 더해 3이 됩니다. 즉, 이 위치에서 가장 큰 정사각형의 변의 길이는 3이 되고, 이 정사각형의 넓이는 3x3입니다. 이 과정이 계속해서 적용되어, 최종적으로 DP 테이블은 아래와 같이 완성됩니다.

1 1 1 0
1 2 2 1
1 2 3 2
0 1 2 3

여기서 가장 큰 값이 3이므로, 가장 큰 정사각형의 변의 길이는 3이고, 넓이는 3 * 3 = 9가 됩니다.

따라서, 각 위치에서 왼쪽, 위쪽, 대각선 위쪽 세 방향의 값 중 최소값을 구하고, 그 값에 1을 더하여 현재 위치에서 만들 수 있는 가장 큰 정사각형의 변의 길이를 결정합니다. 이렇게 DP 테이블을 채우면서 가장 큰 정사각형의 변의 길이를 찾고, 그 변의 길이를 제곱하여 넓이를 구하면 최종 답을 얻을 수 있습니다.

DP 테이블을 사용한 이 방식은 매번 이전 계산 값을 재활용하여 효율적으로 문제를 해결할 수 있게 해주며, 배열의 크기에 비례하는 시간 복잡도를 가집니다.

2. 접근 방식

각 위치에서 만들 수 있는 가장 큰 정사각형 크기를 구하기 위해 Dynamic Programming을 활용합니다. 이 방식에서는 배열의 각 위치를 기준으로 정사각형의 변의 길이를 계산하며, 가장 큰 정사각형을 찾습니다.

1. 초기화: 2차원 배열의 첫 번째 행과 열의 값은 그 자체로 정사각형이 될 수 있습니다. 따라서 첫 번째 행과 열의 값들을 DP 테이블에 그대로 복사하며, 이때 초기 최대 정사각형 크기도 함께 추적합니다. 첫 번째 행과 열에서는 인접한 값이 없기 때문에, 해당 값이 1이면 크기 1의 정사각형을 형성할 수 있습니다.
2. DP 테이블 계산: 배열의 나머지 위치는 왼쪽, 위쪽, 대각선 위쪽의 값을 기준으로 계산됩니다. 현재 위치에서 가장 큰 정사각형을 만들려면, 해당 위치의 왼쪽, 위쪽, 대각선 위쪽 값 중 최소값에 1을 더한 값이 됩니다. 이렇게 각 위치별로 정사각형의 크기를 갱신하면서 최대 크기를 누적합니다.
3. 최종 결과 도출: DP 테이블의 모든 값을 계산한 후, 그중에서 가장 큰 값을 찾아 정사각형의 변의 길이로 사용합니다. 이 변의 길이를 제곱하여 넓이를 구하며, 최종적으로 가장 큰 정사각형의 넓이를 반환합니다.

3. DP 테이블 초기화 및 첫 번째 행, 열 처리

먼저 DP 테이블을 초기화하고, 각 위치에서 정사각형의 크기를 계산할 수 있도록 준비합니다. 이때, 배열의 첫 번째 행과 첫 번째 열은 그 자체로 처리되므로 별도로 초기화해줍니다.

int rows = board.length;
int cols = board[0].length;
int max = 0;  // 최대 정사각형 변의 길이 저장

int[][] dp = new int[rows][cols];  // dp 배열 선언

// 첫 번째 행과 첫 번째 열 초기화
for (int i = 0; i < rows; i++) {
    dp[i][0] = board[i][0];
    max = Math.max(max, dp[i][0]);  // 첫 열에서 최대값 갱신
}
for (int j = 0; j < cols; j++) {
    dp[0][j] = board[0][j];
    max = Math.max(max, dp[0][j]);  // 첫 행에서 최대값 갱신
}

4. DP 테이블 업데이트

이 단계에서는 각 칸에 대해 좌, 상, 대각선 값을 기반으로 현재 위치에서 만들 수 있는 가장 큰 정사각형을 계산합니다. 이를 통해 배열 전체에서 가능한 가장 큰 정사각형을 찾을 수 있습니다.

for (int i = 1; i < rows; i++) {
    for (int j = 1; j < cols; j++) {
        // 현재 위치가 1인 경우 DP 테이블 및 최대값 갱신
        if (board[i][j] == 1) {
            dp[i][j] = minimum(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;  // 좌, 상, 좌상 대각선 값 중 최소값 + 1
            max = Math.max(max, dp[i][j]);  // 최대 정사각형 변의 길이 갱신
        }
    }
}

5. 최종 결과 도출

최종적으로 구한 최대 정사각형의 변의 길이를 제곱하여 가장 큰 정사각형의 넓이를 구하고 반환합니다.

// 가장 큰 정사각형의 넓이를 반환
return max * max;

󰄉 Complexity

• ⏳ TC: O(n * m)
• 💾 SC: O(n * m)

2차원 배열의 각 칸을 한 번씩 탐색하며, 각 칸에서 DP 값을 갱신하므로 시간 복잡도는 O(n * m)입니다. 또한 DP 테이블을 저장하기 위한 추가적인 공간이 필요하므로 공간 복잡도 역시 O(n * m)입니다.