BOJ_1915 : 가장 큰 정사각형

👉 문제링크

---

---

🔸 문제 분석 🔸

• n * m 배열에서 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다.

🔸 문제 풀이 🔸

• 먼저 Brute Force로 풀이 시 시간 복잡도를 계산해 보았다.
  • 정사각형의 오른쪽 아래 꼭짓점을 찾는다고 생각했을때, 한 점을 찍고 최대로 그릴 수 있는 정사각형을 찾아야 한다.
  • 실제로는 최대로 그려지는 값을 찾아야 해서 더 걸리겠지만,
    그려지는 정사각형의 한 변의 길이가 k라고 했을 때,어림잡아서 시간 복잡도는 O(n*m*k*k)이다.
  • 따라서 1,000 ^ 4 = 1조로 시간 제한인 1초를 가뿐히 넘게 된다.
• 2차원 배열 형식에서 효율을 높이고자 하는 경우여서 DP를 의심하고 점화식을 찾기위해 노력했다.
  • 명쾌한 점화식 대신 손으로 적어보며 row, col 합배열을 만든 뒤 dp 배열을 만드는 형식으로 어떻게든 풀어냈다.
  • 정답을 맞은 뒤에 gpt를 통해 점화식을 효율적으로 만들어 보았는데, 그냥 현재 인덱스의 왼쪽, 위쪽, 왼쪽위 대각선 세 인덱스 값 중 최소값에 +1 하면 되는 형식이었다.

🔸 기존 풀이 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n + 1][m + 1];
        int[][] rowSeq = new int[n + 1][m + 1];
        int[][] colSeq = new int[n + 1][m + 1];
        int[][] square = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Character.getNumericValue(chars[j - 1]);
            }
        }

        // Row fill
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] == 1) {
                    rowSeq[i][j] = rowSeq[i][j - 1] + 1;
                }
            }
        }

        // Col fill
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[j][i] == 1) {
                    colSeq[j][i] = colSeq[j - 1][i] + 1;
                }
            }
        }

        // Square fill
        int max = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] == 0)
                    continue;

                int min = Math.min(rowSeq[i][j], colSeq[i][j]); // 가로세로 연속 min개 있음
                if (square[i - 1][j - 1] >= min - 1) { // 좌상단 대각선에 min-1 크기 정사각형 있음
                    square[i][j] = min;
                } else if (square[i - 1][j - 1] + 1 <= min) {
                    square[i][j] = square[i - 1][j - 1] + 1;
                } else {
                    square[i][j] = 1;
                }
                max = Math.max(max, square[i][j]);
            }
        }

        // Output
        bw.write(Integer.toString(max * max));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• arr 배열에 입력 정보를 저장하고, rowSeq 와 colSeq에 가로 오른쪽, 세로 아래쪽으로 합배열을 만들었다.
• 그리고 사실상 dp배열인 square배열에 정사각형 오른쪽아래 인덱스를 두고 가장 큰 정사각형의 한 변의 길이를 저장하며 계산을 진행했다.
  • arr 배열 값이 0인 경우는 사각형을 그릴 수 없으므로 넘어갔다.
  • 가로 세로 연속값 중 작은 값(min)을 골라 정사각형을 그릴 수 있는지 판단한다.
  • square 배열에서 좌상단 인덱스를 살펴보고 정사각형의 내부가 1로 차있는지 확인한다. min값으로 바로 윗쪽과 왼쪽은 1이 차있다는 것을 알고 있으므로, 좌상단 인덱스가 차있으면 정사각형을 그릴 수 있다.
  • 이때, 좌상단 인덱스의 값이 min - 1보다 작으면 min 보다 작은 정사각형으로 그려지는지 확인해야한다.
    좌상단 인덱스 값 + 1이 min 이하이면 그 값으로 정사각형을 그린다.
  • 마지막으로 모두 해당하지 않으면 square에 1을 저장한다.
• square에 저장된 값 중 최대값의 제곱을 출력한다.

 

🔸 점화식 개선 풀이 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];
        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                arr[i][j] = Character.getNumericValue(chars[j]);
            }
        }

        int max = 0; // 첫 번째 행과 열을 고려하여 max 초기화를 0으로 설정

        // copy first col and check max
        for (int i = 0; i < n; i++) {
            dp[i][0] = arr[i][0];
            max = Math.max(max, dp[i][0]); // 첫 번째 열에 대한 최대값 확인
        }
        // copy first row and check max
        for (int j = 0; j < m; j++) {
            dp[0][j] = arr[0][j];
            max = Math.max(max, dp[0][j]); // 첫 번째 행에 대한 최대값 확인
        }


        // DP
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (arr[i][j] == 0)
                    continue;
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }

        // Output
        bw.write(Integer.toString(max * max));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 깔끔하게 DP 점화식이 나온 풀이이다.
  • dp배열의 인덱스를 정사각형의 우하단 인덱스로 보고, 위 풀이와 마찬가지로 정사각형의 한 변의 길이를 저장하는 방식으로 진행한다.
  • 점화식은 min(왼쪽, 위쪽, 좌상단) + 1 이다.
• dp배열을 채우기 전에 초기값으로 첫 번째 열과 행은 기존 입력 값을 복사해주어야 한다.
• 초기값과 dp배열 계산 시 최대값 확인해서 제곱 값을 출력한다.

---

🔸 end 🔸

•  제한 시간 1초인걸 보고, 바로 dp문제인걸 눈치챘다. 하지만 점화식 도출이 어려워서 여러 방향으로 합배열을 그려보거나 하면서 규칙을 찾고자 했다.
• 결국 풀어는 냈는데, 효율이 좋지 않아서 GPT를 통해 점화식을 다시 도출해서 조금 더 효율 좋게 재풀이했다.
• 재풀이 과정에서 첫 행과 열에 초기값을 넣는 반복문에도 최대값 도출이 필요했어서 한번 틀렸다.