[프로그래머스] 가장 큰 정사각형 찾기(Java) — DP 점화식

📌 핵심 요약

• 상태 정의 — dp[i][j] = (i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이
• 점화식 — 왼쪽 · 위 · 대각선 세 값 중 최솟값 + 1. 가장 작은 값이 정사각형 확장의 병목이 된다
• 반환값 주의 — 문제가 요구하는 것은 한 변의 길이가 아니라 넓이(max × max)

 

목차

1 문제 소개

Programmers #12905

가장 큰 정사각형 찾기

board 크기 ≤ 1,000 × 1,000

난이도: Level 2

0과 1로 이루어진 2차원 배열이 주어질 때, 1로만 채워진 가장 큰 정사각형을 찾아 그 넓이를 반환하는 문제다.

풀이 과정

1. 모든 정사각형을 완전 탐색으로 검사하면 1,000 × 1,000 보드에서 시간 초과가 나므로 DP로 접근한다.
2. dp[i][j]를 "(i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이"로 정의한다.
3. 왼쪽, 위, 대각선 세 칸의 dp 값 중 최솟값에 1을 더해 현재 칸의 값을 계산한다.
4. 전체 순회 중 최댓값을 기록하고, 마지막에 제곱하여 넓이로 반환한다.

2 접근 — 점화식 세우기

처음에는 각 칸에서 가능한 모든 크기의 정사각형을 직접 검사하는 방법을 떠올렸지만, 보드가 최대 1,000 × 1,000이라 완전 탐색으로는 시간 초과가 명확했다. 그래서 DP로 방향을 잡았다.

상태 정의

dp[i][j]를 "(i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이"로 정의했다.

이렇게 정의하면 어떤 칸의 답이 이미 계산해 둔 이웃 세 칸(왼쪽, 위, 대각선)의 답만으로 결정된다.

왜 min인가

(i, j)를 꼭짓점으로 하는 정사각형이 한 변 k가 되려면, 왼쪽 · 위 · 대각선 각각을 꼭짓점으로 하는 정사각형이 최소 k-1 이상이어야 한다. 세 방향 중 하나라도 짧으면 그만큼밖에 확장할 수 없으므로, 세 값 중 가장 작은 값이 병목이 된다.

 

점화식

dp[i][j] = min(왼쪽, 위, 대각선) + 1   // board[i][j] == 1 일 때

예시

 

trace — 3×3 보드

board:          dp:
1 1 1           1 1 1
1 1 1     →    1 2 2
1 1 1           1 2 3

dp[2][2]를 구할 때 3×3 정사각형 전체를 다시 검사하지 않는다.

이미 계산해 둔 이웃 세 칸의 값 min(2, 2, 2) + 1 = 3만 보면 된다. 반대로 대각선 어딘가에 0이 있으면 min이 그 지점에서 끊겨, 더 큰 정사각형이 만들어질 수 없다는 사실을 점화식이 자연스럽게 잡아낸다.

ℹ️

점화식이란

앞의 답을 이용해 다음 답을 만드는 규칙이다. 피보나치의 f(n) = f(n-1) + f(n-2)처럼, f(n)을 직접 구하는 공식은 없어도 이전 답들과의 관계만 알면 작은 것부터 차례대로 전부 구할 수 있다. DP는 상태 정의 → 점화식 → 초기값 세 가지로 이루어진다.

3 전체 코드

 

Java — Solution.java

class Solution {
    public int solution(int[][] board) {
        int max = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 첫 행/첫 열은 대각선을 참조할 수 없으므로 원본 값 유지
                if (i > 0 && j > 0 && board[i][j] == 1) {
                    board[i][j] = Math.min(board[i - 1][j],
                                  Math.min(board[i][j - 1], board[i - 1][j - 1])) + 1;
                }
                max = Math.max(board[i][j], max);
            }
        }

        return max * max; // 한 변의 길이가 아닌 넓이 반환
    }
}

i > 0 && j > 0 조건으로 첫 행과 첫 열을 걸러내면, 해당 칸들은 board 값이 그대로 초기값 역할을 한다.

별도의 경계 처리 코드를 두지 않고 조건 하나로 해결했다.

또한 별도의 dp 배열을 만들지 않고 원본 board를 DP 테이블로 재사용하여 추가 메모리 없이 처리했다.

💡

max 갱신 위치

max 갱신을 if 블록 바깥에 둔 것이 포인트다. if 안에 두었다면 [[0,0],[1,0]]처럼 DP 갱신이 한 번도 일어나지 않는 보드에서 max가 0으로 남아 오답이 된다. 1이 하나라도 있으면 넓이 1은 보장되어야 하므로, 갱신은 모든 칸에서 이루어져야 한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.