BOJ 백준온라인져지 1915 가장 큰 정사각형 풀이

문제 설명

1 로 색칠 된 크기가 가장 큰 정사각형의 크기를 구하면 된다.

1 칸은 1 이다.

풀이

정사각형의 조건 가로, 세로의 길이가 같다.

dp 를 이용해서 풀이하기 위해 맨 위부터 오른쪽으로 가면서 차례대로 밑으로 내려갔다.

현재의 위치에서 왼쪽의 길이와 세로의 길이가 같다면 최소한 맨 왼쪽 위를 제외하고 정사각형이 된다는 조건이다.

그러면 맨 왼쪽 위는 어떻게 검사하냐?

왼쪽 위의 대각선을 보면 된다.

결론적으로는 왼쪽, 위, 대각선 왼쪽 위 중 가장 작은 값 + 1를 해주면 된다.

그리고 넓이를 구하는 문제이니 제곱으로 출력해주면 된다. (정사각형 넓이)

코드

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/1915
	* BOJ 백준온라인져지 1915 가장 큰 정사각형 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String args[]) throws IOException {
	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());
	int dp[][] = new int[N + 1][M + 1];
	int result = 0;
	for (int i = 1; i <= N; i++) {
	String str = br.readLine();
	for (int j = 1; j <= M; j++) {
	if (str.charAt(j - 1) == '1') {
	result = Math.max(result, dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1);
	}
	}
	}
	bw.write(String.valueOf(result * result));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

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