[백준] 1915번 : 가장 큰 정사각형

문제

 

 

접근 방식

1인 부분으로만 이루어진 정사각형 중 가장 큰 정사각형을 찾아야 한다.

1

11
11

111
111
111

 

위와 같이 1로만 이루어진 곳을 찾아야 하는데

1인 곳을 발견할 때마다 주변을 한 칸씩 넓혀가며 모두 1인지 확인하는 것은

시간초과가 날 것이 확실하기 때문에 그렇게 무식하게 풀 수는 없다.

00
01

 

위의 경우를 생각해보면 1 주변은 모두 0이기 때문에 정사각형이 될 수 없고

크기가 1인 정사각형 하나만 가능하다.

11
11 <

 

위의 경우라면 오른쪽 맨 아래의 1을 기준으로 주변 3개가 모두 1이니

크기가 4인 정사각형을 만들 수 있다.

01
11

 

하지만 위와 같이 하나라도 1이 아니라면 각각 크기가 1인 정사각형만 만들 수 있고

결국 자기 주변의 칸들이 모두 1이라면 길이가 1 더 긴 정사각형을 만들 수 있다는 것이다.

0111
0111
0111

 

위의 경우를 예시로 DP 테이블을 채우는 과정을 살펴보면 아래와 같다.

01

011

0111

0111
0

0111
01

0111
012

0111
0122

0111
0122
0

0111
0122
01

0111
0122
012

0111
0122
0122

 

첫 행과 열에 등장한 1은 위나 옆을 살펴볼 수 없으니 무조건 1이 될 것이고

이후에 등장한 1들은 주변 3칸을 살펴봐서 모두 1이라면

기존보다 길이가 1긴 정사각형을 만들 수 있으니 0 > 1 > 2 ... > n 순으로

길이를 늘려주기만 하면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");

		int n = Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		int max = 0;

		int[][] dp = new int[n][m];
		int[] dx = {-1, -1, 0};
		int[] dy = {-1, 0, -1};

		for (int i = 0; i < n; i++) {
			input = br.readLine().split("");
			for (int j = 0; j < m; j++) {
				if (Integer.parseInt(input[j]) != 1) continue;

				int min = Integer.MAX_VALUE;

				for (int dir = 0; dir < 3; dir++) {
					int x = i + dx[dir];
					int y = j + dy[dir];

					if (x < 0 || y < 0) {
						min = 0;
						break;
					}

					min = Math.min(min, dp[x][y]);
				}

				dp[i][j] = min + 1;
				max = Math.max(max, dp[i][j]);
			}
		}

		System.out.println(max * max);
	}
}