[BOJ] 1915 : 가장 큰 정사각형 [G4]

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

 

 

 

 

 

[문제]

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

[입력]

 

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

[출력]

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

[예제 입력 1]

4 4
0100
0111
1110
0010

[예제 출력 1 ]

4

 

 

---

 

 

[내 풀이]

 

dp를 이용해 풀었습니다.

 

N * M의 배열을 입력받은 후,

(r, c)에서 1이라는 숫자를 만났을 때, (r-1, c-1)의 숫자를 확인하여 해당 좌표의 숫자값이 0이 아니면

map[r-1][c-1] + 1만큼의 정사각형을 만들 수 있는지 확인후 만들 수 있다면

map[r][c]의 좌표를 정사각형 한변의 길이로 업데이트 해주었습니다. 

 

 

package SSAFY.BOJ.dp;

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

public class BJ_1915_가장큰정사각형 {

    static int N, M;
    static int[][] map;
    static boolean[][] isVisited;
    static int max_square;

    static void check(int r, int c) {

        // 맵의 끝이거나 이 전에 정사각형이 만들어지지 않았을 경우
        if (!isIn(r-1, c-1) || map[r-1][c-1] == 0) return;

        int curLen = 1;
        for (int i = 1; i <= map[r-1][c-1]; i++) {
            if (map[r-i][c] == 0 || map[r][c-i] == 0) break;
            curLen = i + 1;
        }

        map[r][c] = curLen;

        max_square = Math.max(max_square, map[r][c]);
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                map[i][j] = line[j] - '0';
                if (map[i][j] == 1) max_square = 1; // 단일 행 고려
            }
        }


        isVisited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    check(i, j);
                }
            }
        }

//        printMap(map);

        System.out.println(max_square * max_square);

    }

    // debug
    static void printMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}