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

백준 1915번 가장 큰 정사각형 (자바)

 

 

 

출처

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

 

 

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

약 2시간..?

DP는 너무 어렵다.

 

 

 

접근 방법

처음에는 현재 위치(i,j)를 기준으로 (i, j-1), (i-1, j)만 검사하면 되는 줄 알고 1인 경우 넓이를 구했지만 어림도 없었다.

1을 발견할 때마다 (i,j-1), (i-1, j), (i-1, j-1) 세 좌표를 모두 검사해 2x2정사각형을 만족했을 때 현재 위치에 한 변의 길이를 넣어주는 식으로 진행했다.

이러한 과정을 계속해가면서 1이거나 1이상의 값들을 만나는 경우 조건을 만족하면 정사각형이므로 변의 길이를 갱신한다.

 

 

 

 

내 코드

	package dynamicprogramming;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class TheBiggestSquare {
	/**
	* 백준 1915 가장 큰 정사각형 (https://www.acmicpc.net/problem/1915)
	*/
	public static void main(String[] args) throws IOException {
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(reader.readLine());
	int n = Integer.parseInt(st.nextToken());
	int m = Integer.parseInt(st.nextToken());
	int[][] dp = new int[n+1][m+1];
	int max = Integer.MIN_VALUE;
	for (int i=1; i<=n; i++) {
	String input = reader.readLine();
	for (int j=1; j<=m; j++) {
	dp[i][j] = input.charAt(j-1) - '0';
	if (dp[i][j] == 0) {
	continue;
	}
	int min = Integer.MAX_VALUE;
	if (min > dp[i-1][j]) {
	min = dp[i-1][j];
	}
	if (min > dp[i-1][j-1]) {
	min = dp[i-1][j-1];
	}
	if (min > dp[i][j-1]) {
	min = dp[i][j-1];
	}
	dp[i][j] = min+1;
	if (max < dp[i][j]) {
	max = dp[i][j];
	}
	}
	}
	System.out.println(max*max);
	}
	}

view raw TheBiggestSquare.java hosted with ❤ by GitHub

 

 

 

고려할 점

1. DP 사용할 것

2. 변의 길이를 이용해 넓이를 구할 것