[백준 알고리즘/BOJ] 자바(java) 1915번 가장 큰 정사각형

1915번: 가장 큰 정사각형

 

문제

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개의 숫자로 배열이 주어진다.

출력

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

 

 

 

 

 

처음엔 DP(Dynamic programming)로 풀 생각을 안하고 무작정 배열을 탐색해서 1이 삼각형 모양으로 있는지를 판단하는 코드를 작성했다. 코드가 엄청 더러웠지만 이클립스에선 제대로 작동했고, 무슨 이유에선지 백준에서는 틀렸다고 나왔다.. 도저히 이 후로 어떻게 고쳐야 할지 모르겠어서 (https://simju9397.tistory.com/27)를 참고했다. 알고리즘에 대한 개념을 다 잊어버린 채로 무작정 백준 문제만 풀려고 했던 것 같다.. 알고리즘 복습을 꾸준히 해야겠다.

 

먼저 square 배열을 입력받을 때, 입력한 값이 1이면 dp 배열에도 1이 대입되기 때문에 처음에는 dp와 square 배열이 같은 값을 가진다. isSquare() 함수에서 square 값이 1인 경우, (아래 표에서 회색으로 표시한 부분) 세 값 중 가장 작은 값을 찾아 1을 더한 값이 find[i][j] 값이 된다. square 값을 비교하지 않고 find 값을 비교한 이유는, for문이 진행되면서 find값이 누적되어 변의 길이가 2 이상인 값을 찾을 수 있기 때문이다. (square 배열은 0과 1으로만 이루어져 있기 때문에 변의 길이가 최대 2) 처음엔 비교할 세 개의 값이 모두 1인 경우에만 find[i][j]을 변경하는 코드를 작성했었는데, square 값이 1이고 비교할 세 개의 값 중 하나라도 0이면, 0+1이 되므로 원래대로 find값이 1이 된다.

find[i-1][j-1]	find[i-1][j]
find[i][j-1]	find[i][j]

 

(설명 더 자세하게 수정하기)

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

public class B_1915 {
	static int[][] square;
	static int[][] dp;
	static int n, m;
	static int r = 0;
	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());
		
		square = new int[n][m];
		dp = new int[n][m];
		
		for(int i=0;i<n;i++) {
			String s = br.readLine();
			for(int j=0;j<m;j++) {
				square[i][j] = s.charAt(j) - '0';
				if(square[i][j] == 1) {
					dp[i][j] = 1;
					r = 1;
				} 
			}
		}
		
		isSquare();
		System.out.println(r * r);
	}
	static void isSquare() {
		for(int i=1;i<n;i++)
			for(int j=1;j<m;j++) {
				if(square[i][j] == 1)
					dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
				if(r < dp[i][j]) r = dp[i][j]; // 한 변의 최대값 찾기
			}
	}
}