[JAVA] 백준 (골드4) 1915번 가장 큰 정사각형

링크

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

---

문제 설명

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

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

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

---

입력 예제

4 4
0100
0111
1110
0010

---

출력 예제

4

---

풀이

2차원 배열에서 1로 된 가장 큰 정사각형의 넓이를 구해야 한다. 그래프 탐색으로 접근할 경우 모든 원소에 대해 탐색하며 또 정사각형 내부의 원소들까지 확인을 해야하므로 $O(n^3)$에 가까운 비효율적인 연산이 발생한다. 따라서 정사각형의 한 변의 길이를 저장하여 DP로 문제를 해결해야 한다.

dp배열을 다음과 같이 정의한다.

dp[i][j]: (i, j)를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이

오른쪽 아래를 기준으로 하므로, (i-1, j), (i-1, j-1), (i, j-1)를 생각해봐야 하는데 배열이 다음과 같다면

1 1
1 1

dp[2][2]는 정사각형의 한 변의 길이인 2가 저장되어야 한다. 이는 인접 좌표들의 dp값 중 최솟값에 1을 더한 것과 같다. 여기서는 모두 1로 동일하므로 dp[2][2] = 1 + 1이 된다.

배열이 다음과 같다면

1 0 
1 1

dp[2][2]는 자기 자신만 포함하므로 1이 저장되어야 한다. 여기서는 dp[1][2] = 0이므로 dp[2][2] = dp[1][2] + 1이 된다.

배열이 다음과 같다면

1 1 1
1 1 1
1 0 1

한 변의 길이가 2인 정사각형이 2개가 나오므로 dp[2][2] = 1 + 1가 되고, dp[2][3] = 1 + 1이 된다. 여기서 dp[3][3]은 인접 좌표 중에 0이 존재하므로 1보다 큰 정사각형이 만들어지지 않으므로 dp[3][3] = 0 + 1이 된다.

이를 Bottom-Up 방식으로 구현하면 다음과 같다.

int maxSide = 0;  //가장 큰 정사각형의 한 변의 길이
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        if (arr[i][j] == 1) {  //현재 원소가 1일 경우
            dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]),
                    dp[i - 1][j - 1]) + 1;
            maxSide = Math.max(maxSide, dp[i][j]);
        }
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        //dp[i][j]: (i, j)를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이
        int[][] dp = new int[N + 1][M + 1];  //1-based index
        int[][] arr = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String line = br.readLine();
            for (int j = 1; j <= M; j++) {
                //해당 위치의 문자를 숫자(int)로 변환
                arr[i][j] = line.charAt(j - 1) - '0';
            }
        }

        int maxSide = 0;  //가장 큰 정사각형의 한 변의 길이
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] == 1) {  //현재 원소가 1일 경우
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]),
                            dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        System.out.println(maxSide * maxSide);
    }
}