1915 - 가장 큰 정사각형(Java)

문제 개요 💡

이 문제에서는 N x M 크기의 0과 1로 이루어진 맵에서, 1로만 이루어진 가장 큰 정사각형을 찾는 문제였음.
주어진 맵에서 가장 큰 정사각형의 넓이를 구해야 했음.

---

초기 접근 및 문제점 🚧

처음에는 동적 계획법(DP)을 사용해 문제를 풀기로 했음.
각각의 칸에서, 그 칸을 우측 하단으로 하는 가장 큰 정사각형의 한 변의 길이를 구할 수 있었음.
DP 테이블을 사용하여 계산하려 했지만 몇 가지 문제에 직면했음.

DP 테이블 설계 📊

• dp[i][j]: (i, j) 위치를 우측 하단으로 하는 가장 큰 정사각형의 한 변의 길이
• map[i][j]: 주어진 맵의 값 (1 또는 0)

상태 전이

dp[i][j]는 다음과 같이 계산할 수 있었음:

• dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 (단, map[i][j]가 1일 경우에만 계산)

---

문제점 1: "1로만 이루어진 가장 큰 정사각형"을 찾는 과정에서 오류 발생 🚫

문제 발생

처음 구현한 isLeftAndUpAllOne 함수에서는, dp[i-1][j-1] 값을 기준으로 그 크기만큼 위쪽과 왼쪽 칸들을 검사하려 했음.
하지만 dp[i-1][j-1] 값에 맞춰서 진행하는 방법이 잘못되어 오류가 발생했음. 이 방식은 일부 반례에서 올바르게 동작하지 않았음.

오타 수정

잘못된 코드:

private static boolean isLeftAndUpAllOne(int x, int y) {
    for (int i = 1; i <= dp[x - 1][y - 1]; i++) {
        if (map[x - i][y] != 1) return false;
        if (map[x][y - 1] != 1) return false;
    }
    return true;
}

수정된 코드

• 조건문을 수정하여, 왼쪽과 위쪽을 모두 검사하는 방식으로 변경했음.
  (x, y)에서 위쪽과 왼쪽 칸이 모두 1인지 확인하며, 그 중 최소값을 기준으로 진행할 수 있었음.

private static boolean isLeftAndUpAllOne(int x, int y) {
    for (int i = 1; i <= dp[x - 1][y - 1]; i++) {
        if (map[x - i][y] != 1) return false;
        if (map[x][y - i] != 1) return false;
    }
    return true;
}

---

문제점 2: 초기값 설정 문제 ⚠️

문제 발생

answer의 초기값이 0으로 설정되어 있어, 가장 큰 정사각형의 한 변이 1일 때 결과가 0으로 출력되는 오류가 발생했음.

해결 방법

answer의 초기값을 1로 수정하여 문제를 해결할 수 있었음.

private static int answer = 1;

---

문제점 3: 모든 가능한 크기 확인 누락 ⚡

주어진 반례에서, 예를 들어 4x4 맵에서 dp[i-1][j-1]이 2인 경우, 단순히 dp[i][j]가 3이 되는 것만 확인하는 방식이었음.
하지만 실제로는 1부터 3까지의 크기 중 가능한 경우를 모두 확인해야 했음.

해결책

최대 크기를 찾을 수 있는 방법을 수정했음.
dp[i][j]를 갱신하는 함수에서 가능한 크기들을 모두 확인하도록 하였음.

private static int getMaxSize(int x, int y) {
    for (int i = 1; i <= dp[x - 1][y - 1]; i++) {
        if (map[x - i][y] != 1) return i;
        if (map[x][y - i] != 1) return i;
    }
    return dp[x - 1][y - 1] + 1;
}

---

최종 코드 📋

최종적으로 아래와 같은 코드로 문제를 해결할 수 있었음:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;
    private static int[][] dp;
    private static int[][] map;
    private static int answer = 0;

    public static void main(String[] args) throws IOException {
        inputSetting();
        findAnswer();
        System.out.println(answer * answer);
    }

    private static void findAnswer() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1) {
                    dp[i][j] = getMaxSize(i, j);
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }
    }

    private static int getMaxSize(int x, int y) {
        for (int i = 1; i <= dp[x - 1][y - 1]; i++) {
            if (map[x - i][y] != 1) return i;
            if (map[x][y - i] != 1) return i;
        }
        return dp[x - 1][y - 1] + 1;
    }

    private static void inputSetting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][M + 1];
        map = new int[N + 1][M + 1];
        for (int i = 0; i < N; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i + 1][j + 1] = tmp.charAt(j) - '0';
            }
        }
    }
}

---

결론 🎯

개선한 점

1. 오타 수정: isLeftAndUpAllOne 함수에서 인덱스 비교 오류를 수정했음.
2. 초기값 설정: answer 초기값을 1로 설정하여 가장 작은 정사각형을 제대로 처리했음.
3. 모든 크기 확인: dp[i][j]를 계산할 때, 가능한 크기들에 대해 모두 확인할 수 있도록 수정했음.

배운 점 💡

1. 동적 계획법(DP)을 활용할 때는 배열 인덱스의 범위를 정확히 관리하는 것이 중요했음.
2. 문제를 해결할 때는 항상 경계 값과 예외 처리를 철저히 확인해야 했음.