[백준 1915] 가장 큰 정사각형 (JAVA)

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

1915번: 가장 큰 정사각형

 

dp를 사용해서 해결할 수 있었다.

 

ㅁㅁㅁㅁ

ㅁㅁㅁㅁ

ㅁㅁㅁㅁ

ㅁㅁㅁㅁ

 

이런식으로 왼쪽, 위, 왼쪽 대각선 부분을 확인하여 해당 위치들에서 가장 작은 값에 +1한 값을 넣는다. 

그리고 그 값이 가장 큰 값인지 확인한다.

 

ex)

1 1 1 0

1 1 1 0

1 1 1 0

1 1 1 1

인덱스의 시작은 (1,1) 이다!

 

(1,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 다 0이므로  0+1 값을 넣는다.

(1,2)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 0이므로  0+1 값을 넣는다.

(1,3)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 0이므로  0+1 값을 넣는다.

(1,4)에 0이 존재하므로 스킵

(2,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 0이므로  0+1 값을 넣는다.

(2,2)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 1이므로  1+1 값을 넣는다.

-> 현재 기준 최댓값은 (2,2)의 2이므로 최댓값을 2로 세팅

1 1 1 0

1 2 1 0

1 1 1 0

1 1 1 1

 

(2,3)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 1이므로  1+1 값을 넣는다.

-> 

1 1 1 0

1 2 2 0

1 1 1 0

1 1 1 1

 

(2,4)에 0이 존재하므로 스킵

(3,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 0이므로  0+1 값을 넣는다.

(3,2)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 1이므로  1+1 값을 넣는다.

->

1 1 1 0

1 2 2 0

1 2 1 0

1 1 1 1

(3,3)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 2이므로  2+1 값을 넣는다.

-> 현재 기준 최댓값은 (3,3)의 3이므로 최댓값을 3로 세팅

1 1 1 0

1 2 2 0

1 2 3 0

1 1 1 1

(3,4)에 0이 존재하므로 스킵

 

(4,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 0이므로  0+1 값을 넣는다.

(4,2)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 1이므로  1+1 값을 넣는다.

(4,3)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 가장 작은 값은 1이므로  1+1 값을 넣는다.

(4,4)에 0이 존재하므로 스킵

 

따라서, 최대 넓이 값은 3*3 = 9 이다!

 

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

public class Main {

	static int[][] arr;
	static int result = 0, n, m;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			String str = br.readLine();
			for (int j = 1; j <= m; j++) {
				arr[i][j] = str.charAt(j - 1) - '0';
			}
		}

		if (n == 1 && m == 1) {
			System.out.println(arr[1][1]);
			return;
		}

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

		System.out.println(result*result);

	}

}