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

🔗 문제링크

코딩테스트 연습 - 가장 큰 정사각형 찾기

📂 분류

DP

💡 풀이

DP Bottom-up 방식으로 해결되는 문제이다.

접근방식

• 정 사각형의 넓이를 구하는 문제이기 때문에 왼쪽, 위쪽이 하나라도 0이라면 넓이는 1이 된다. 따라서 점화식은 아래와 같이 나온다.

cache[i][j] = Math.min(cache[i - 1][j - 1], Math.min(cache[i - 1][j], cache[i][j - 1])) + 1;

💻 코드

public class Solution {

    private int[][] cache;

    public int solution(int[][] board) {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        init(board, row, col);

        if (row == 1 && col == 1) {
            answer = board[0][0] * board[0][0];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (board[i][j] == 0) {
                    cache[i][j] = 0;
                } else {
                    cache[i][j] = Math.min(cache[i - 1][j - 1], Math.min(cache[i - 1][j], cache[i][j - 1])) + 1;
                    answer = Math.max(answer, cache[i][j]);
                }
            }
        }

        return answer * answer;
    }

    private void init(int[][] board, int row, int col) {
        cache = new int[row][col];

        cache[0][0] = board[0][0];

        for (int i = 0; i < row; i++) {
            cache[i][0] = board[i][0];
        }

        for (int i = 0; i < col; i++) {
            cache[0][i] = board[0][i];
        }
    }
}