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

가장 큰 정사각형 찾기

1과 0으로 채워진 표에서 1로 이루어진 가장 큰 정사각형을 찾는 문제이다.
처음에는 BFS로 1로 이루어진 덩어리를 찾고, 해당 덩어리에서 가장 큰 정사각형을 찾는 방향으로 풀이를 세워봤지만 정사각형을 판별해내는 로직이 떠오르지 않아 포기했다.
다른 사람의 풀이를 찾아보니 다이나믹 프로그래밍 알고리즘으로 풀 수 있는 문제였다.
다이나믹 프로그래밍 문제는 정말 무궁무진한 것 같다.

일단 표의 행 길이와 열 길이를 구해 dp 테이블을 선언한다.

	int rows = board.length;
    int cols = board[0].length;

    // DP 테이블 생성
    int[][] dp = new int[rows][cols];

dp[i][j] : i번째 열, j번째 행의 칸을 포함할 때 만들 수 있는 가장 큰 정사각형의 변의 길이

dp 테이블의 요소가 나타내는 것은 두 가지이다.

• board[i][j]가 1인지 0인지
• 1이라면 가장 큰 정사각형의 변은 얼마인지

dp[i][j]에 board[i][j]가 1인지 여부가 들어가야, 다음 dp[i+1][j]나 dp[i][j+1], dp[i+1][j+1]의 값을 채울 때 올바른 정사각형이 구성되는지 확인하고 값을 채울 수 있다.

그러므로 board[i][j]가 0이라면 dp[i][j] 또한 0이 된다.
해당 칸을 포함하여 만들 수 있는 정사각형은 없기 때문이다.

board[i][j]가 1이라면

---

이러한 이유는 정사각형을 만들기 위함이다.
board[i][j]가 1일 때, dp[i-1][j]의 값에 +1을 한다면, n x (n-1) 크기의 직사각형을 만들게 되는 것이기에, dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최솟값을 고름으로써 board[i][j]를 포함하는 정사각형을 찾을 수 있게 된다.

소스코드

import java.util.Arrays;

public class Solution {
    public int solution(int[][] board) {
        // 행과 열의 크기
        int rows = board.length;
        int cols = board[0].length;

        // DP 테이블 생성
        int[][] dp = new int[rows][cols];

        // 첫 번째 열 초기화
        for (int i = 0; i < rows; i++) {
            dp[i][0] = board[i][0];
        }

        // 첫 번째 행 초기화
        for (int j = 0; j < cols; j++) {
            dp[0][j] = board[0][j];
        }

        // DP 테이블 채우기
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (board[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }

        // 최대 한 변의 길이 찾기
        int maxSide = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dp[i][j] > maxSide) {
                    maxSide = dp[i][j];
                }
            }
        }

        // 정사각형 넓이 반환
        return maxSide * maxSide;
    }
}