[BOJ] 1915: 가장 큰 정사각형 (JAVA)

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

 

풀이

 

참고로 가장 큰 정사각형은 안이 1로 꽉 찬 정사각형을 말한다 !

해당사항이 조건에 명시되어 있지 않아 헷갈렸다.

1	0	1	0
1	1	1	0
1	1	1	1
1	1	1	1

 

예를들어 이런 4x4 사각형 map[][]내에서 가장 큰 정사각형을 찾아야한다고 해보자.

 

참고로, 1이 한 개라도 있을 경우 최소 사각형의 넓이는 1이다.

map에 값을 넣어줄 때 1이 존재할 경우 ans = 1로 갱신해줬다.

그리고 dp배열에도 1 값을 넣어줬다. (추후 계산에 사용하기 위해)

 

A (map[i-1][j-1])	C (map[i-1][j])
B (map[i][j-1])	기준 (map[i][j])

 

그럼 일단, 4분할로 규칙을 찾을 수 있다.

 

1	0	1	0
1	1	1	0
1	1	1	1
1	1	1	1

빨간색 부분의 규칙을 찾아보겠다.

1	1
1	1

🔼 map[][]

1	1
1	2

🔼 dp[][]

 

기준이 1인 경우, A B C가 전부 1이면 이 정사각형은 A,B,C에서 가장 작은수인 1에 1을 더한 값인 2가 된다.

즉, 2x2 사각형이 이곳에 존재한다는 것을 뜻한다.

그럼, dp[i][j]에 A B C 중에 가장 작은 값에 +1을 더한 값을 저장해준다.

그리고 ans는 dp[i][j]와 비교해 더 큰 값으로 갱신한다.

 

반복하면 dp배열은

1	1	1	0
1	2	2	0
1	2	3	1
0	1	2	1

 

이렇게 바뀌게 되는데, 3x3인 정사각형과 2x2정사각형이 존재한다는 것을 알 수 있다.

가장 큰 정사각형의 길이는 3이고, 넓이는 9가 된다.

 

 

전체코드

package 백준renew;

import java.io.*;
import java.util.*;

public class 골드4_1915_가장큰정사각형 {
	static int N, M;
	static char map[][];
	static int dp[][];
	static int ans;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new char[M][N];
		dp = new int[M][N];
		ans = 0;
		
		for(int i=0; i<M; i++) {
			String tmp = br.readLine();
			map[i] = tmp.toCharArray();
		}
		
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]=='1') {
					dp[i][j] = 1;
					ans = 1;
				}
			}
		}
		
		for(int i=1; i<M; i++) {
			for(int j=1; j<N; j++) {
				if(map[i-1][j-1] == '1' && map[i][j-1] == '1' && map[i-1][j]=='1' && map[i][j]=='1') {
					dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j]))+1;
					ans = Math.max(dp[i][j], ans);
				}
			}
		}
		
		sb.append(ans*ans);
		bw.write(sb.toString());
		bw.close();
	}
}