문제

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

1과 0으로 이루어진 NxM크기의 행렬이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형 부분 행렬 찾는 프로그램을 작성하시오.

---

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 개가 주어진다.

---

출력

각 테스트 케이스에 대해서 가장 큰 정사각형의 너비 또는 높이를 출력한다. 만약 그런 정사각형이 없을 때는 0을 출력한다.

---

풀이

접근방법

시간제한 5초, 메모리 256MB이다.
(1 ≤ N,M ≤ 1,000)

1. 전체 테스트 케이스가 몇 개인지 알 수 없다.
2. 5초라는 시간이 여유로워 보이지만 최대 1000x1000 크기의 배열 각 점에서 최대 k로 된 길이를 모두 찾는다면 연산 횟수가 굉장히 많다.

최소한의 연산, 한 번의 스캔으로 크기를 확인할 수는 없을까..?
라는 의문을 가지고 시작한다.

현재 위치에서 가장 큰 정사각형을 찾고 싶다면, 왼쪽, 왼쪽 상단, 위쪽 3 방향을 확인해 보자.

// 예제의 첫번째 입력
4 5
0 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1

일단 저장된 배열에서 1의 값을 찾으면, 최소 1의 정사각형이 완성된다는 의미이다.

(2,2)를 살펴보자.

좌측과 상단에 크기 1의 정사각형이 있다.
하지만 좌상단에는 0의 값을 가진다.

현재 위치에서 1보다 큰 정사각형을 가지기 위해서는 좌상단도 1의 값을 가져야 한다.

4 4
1 1 0 0
1 1 1 0
1 1 1 0
0 0 0 0

(3,3)을 살펴보자.
좌측(2,3)에서 크기 2의 정사각형,
좌상단(2,2)에서 크기 2의 정사각형,
상단(3,2)에서 크기 1의 정사각형이 만들어진다.

이제 식을 생각해 보자.

// i,j 에서 만들 수 있는 가장 큰 정사각형의 크기 => dp[i][j]
조건 1. dp[i - 1][j - 1] > 0
조건 2. dp[i - 1][j] > 0
조건 3. dp[i][j - 1] > 0
을 모두 만족한다면
dp[i][j] = 최솟값(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

그게 아니라면 dp[i][j] = 1

와 같이 정리될 수 있다.
이제 dp 배열에서 가장 큰 값이 만들 수 있는 가장 큰 정사각형의 크기이다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		while (true) {
			String[] splitedLine = in.readLine().split(" ");
			N = stoi(splitedLine[0]);
			M = stoi(splitedLine[1]);
			if (N == 0 && M == 0)
				break;

			int[][] map = new int[N + 1][M + 1];
			int[][] dp = new int[N + 1][M + 1];
			for (int i = 1; i <= N; ++i) {
				splitedLine = in.readLine().split(" ");
				for (int j = 1; j <= M; ++j) {
					map[i][j] = stoi(splitedLine[j - 1]);
				}
			}

			int max = 0;
			for (int i = 1; i <= N; ++i) {
				for (int j = 1; j <= M; ++j) {
					if (map[i][j] == 1) {
						if (dp[i - 1][j - 1] > 0 && dp[i - 1][j] > 0 && dp[i][j - 1] > 0) {
							dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
						} else {
							dp[i][j] = 1;
						}
						max = Math.max(max, dp[i][j]);
					}
				}
			}
			sb.append(max).append("\n");
		}
		System.out.println(sb);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}