백준 1915번 <가장 큰 정사각형>

백준 알고리즘 1915번

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

---

1915번

0과 1로 이루어진 N * M 배열이 있다. 이때, 1로 이루어진 가장 큰 정사각형의 넓이를 구하여라.

 

입력으로 첫 줄에 세로 길이 N과 가로 길이 M이 주어진다.

그 다음 N개의 줄에 걸쳐 배열의 상태가 문자열로 주어진다.

 

출력으로 1로 이루어진 가장 큰 정사각형의 넓이를 구해 출력하면 된다.

---

문제 해결

엄청 많이 틀렸다...

처음엔 (i, j)좌표를 정사각형의 가장 위, 가장 왼쪽 좌표로 보고 만들 수 있는 정사각형을 모두 만들어보는 식으로 했더니 시간초과가 났다.

그 다음에는 만들 수 있는 정사각형의 길이를 이분탐색으로 찾고 만들 수 있는지 확인하는 식으로 했더니 시간초과가 났다.

이제 알고리즘 분류를 봤다. ㅎㅎ... 다이나믹 프로그래밍,,, WOW

어떻게 이 문제가 다이나믹 프로그래밍일까 생각을 해보는데 잘 생각이 안났다. 그러다가 다음날에 문득 풀이 방법이 생각나서 풀 수 있었다. (그럼에도 불구하고 무수히 많은 틀렸습니다...)

 

입력으로 받은 board 배열을 dp 배열로 사용하였다.

board[i][j]의 값은 (i, j) 좌표를 맨 오른쪽, 맨 아래로 하는 정사각형의 한 변의 길이의 최댓값이다.

따라서 정사각형의 한 변의 길이가 짝수일 경우와 홀수일 경우를 나눠서 board[i][j]의 값을 구할 수 있다.

 

짝수일 경우는 쉽다.

위의 그림에서처럼 길이가 4일 때는, 딱 4등분 해서 각 사각형의 맨 오른쪽, 맨 아래 좌표의 값이 2인지 확인하면 된다.

홀수일 경우는 딱 4등분이 안되기 때문에 조금 다르다. 

위의 그림처럼 길이가 5일 때를 보면, 겹쳐지도록 4등분을 해서 확인을 해야 한다.

따라서 확인을 할 때, 작은 사각형의 길이는 5//2 + 1의 값인 3이다. 이렇게 나눠진 사각형의 맨 오른쪽, 맨 아래 좌표의 값이 3인지 확인하면 된다.

 

구현은 (1, 1) 좌표부터 시작해서 순서대로 채우는 식으로 했다.

(i, j) 좌표를 맨 오른쪽, 맨 아래 좌표로 가정해서 for문을 돌려서(len) 만들 수 있는 정사각형을 최대로 만들었다.

이때, 범위를 벗어나거나 정사각형을 만들 수 없다면 해당 for문을 멈춰버린다.

 

틀리면서 알아낸 반례가 조금 있는데 아래의 경우를 처리하니 통과할 수 있었다.

1. 모두 0으로 입력이 들어오는 경우, 모두 1로 입력이 들어오는 경우
2. N이나 M이 1인 경우

---

코드

import javax.sound.midi.Track;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_1915 {
    static int N, M, ANS;
    static int[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                board[i][j] = chars[j] - '0';
            }
        } // end input
        ANS = 0;
        if (init()) ANS = 1;
        process();
        pretty();
        System.out.println(ANS * ANS);
    }
    static boolean init(){
        for (int i = 0; i < N; i++) {
            if (board[i][0] == 1) return true;
        }
        for (int j = 0; j < M; j++) {
            if (board[0][j] == 1) return true;
        }
        return false;
    }
    static void pretty() {
        for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(board[i]));
        }
    }
    static void process(){
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {   // (i, j) 좌표를 정사각형의 맨 오른쪽 맨 아래 좌표로 생각
                if (board[i][j] == 0) continue;     // 0이면 볼 필요 없음
                for (int len = 2; len < Math.min(i + 1, j + 1)+1; len++) {    // 만들 수 있는 정사각형의 길이
                    int half = len / 2;
                    int chk = len / 2;
                    if (len % 2 != 0) chk++;

                    // 범위 벗어나면 더 이상 볼 필요 없음
                    if (i-half < 0 || j-half < 0) break;
                    // 3개가 다 chk과 같거나 크면 len 길이의 정사각형을 만들 수 있음
                    if (board[i-half][j-half] >= chk && board[i-half][j] >= chk && board[i][j-half] >= chk) {
                        board[i][j] = len;
                        ANS = Math.max(len, ANS);
                    } else {
                        break;
                    }
                }
            }
        }
    }

}

---

결과

---

참고한 반례

6 6
001000
001100
011110
111110
001110
000111

9
---------
6 6
001000
001000
011110
101010
001010
000111

1
---------
6 6
000000
000000
000000
000000
000000
000000

0
---------
6 6
111111
111111
111111
111111
111111
111111

36
---------
1 5
11111

1
---------
1 5
00100

1
---------
4 4
1111
1111
1101
1111

4

시간초과났던 코드

import javax.sound.midi.Track;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N, M, ANS;
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        board = new char[N][];
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
        } // end input

        BS();
        System.out.println(ANS * ANS);

    }
    static void BS(){
        int left = 0;
        int right =  Math.min(N, M);
        while (left <= right) {
            int mid = (left + right) / 2;
            if (process(mid)) { // mid만한 정사각형이 있음. 크기를 키워봐
                ANS = Math.max(ANS, mid);
                left = mid+1;
            }else{  // mid만한 정사각형이 없음. 크기를 줄여봐
                right = mid-1;
            }
        }
    }

    static boolean process(int len) {
        for (int i = 0; i < N - len; i++) {
            for (int j = 0; j < M - len; j++) {
                if (check(i, j, len)) {
                    return true;
                }
            }
        }
        return false;
    }
    static boolean check(int I, int J, int len) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if(board[I+i][J+j] == '0') return false;
            }
        }
        return true;
    }

}