[자바] 백준 1915번: 가장 큰 정삼각형

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

1915번: 가장 큰 정사각형

 

dp로 푼 문제

 

입력받는 순서대로 dp를 채워나간다.

 

현재 칸의 값이 0이면 dp[현재칸][]에도 0을 넣는다.

현재 칸의 값이 1이면,

내 왼쪽,

내 윗쪽,

내 위에서 왼쪽

이 세 칸의 값을 봐야 한다.

세 칸의 값을 보고 세 값 중 최솟값을 가져와서,

dp[현재칸][]=최솟값+1을 하면 된다.

 

(왜 이렇게 동작하는지는 그림을 그려보면서 생각해보자)

 

우선 현재칸의 값이 0이면

이 칸을 포함한 정사각형은 만들수가 없으니 0,

 

현재칸의 값이 1이면..

우선 나 혼자서는 1칸짜리 정사각형을 만들 수 있는데

내 왼쪽,윗쪽,왼-윗쪽 세 칸도 모두 1이라면면, 현재칸까지 포함해서 2*2 사각형을 만들 수 있다.

1	1
1	2

만약 

내 왼쪽,윗쪽,왼-윗쪽 세 칸이 모두 2라면? 

왼쪽,윗쪽,왼-윗쪽칸 모두 자신만의 2*2영역 사각형을 갖고있으니 이 영역을 포함시키고

현재칸도 포함시키면 3*3사각형을 만들 수 있다.

1	1	1
1	2	2
1	2	3

 

 

만약 세 칸의 값이 각각 2,2,1이라면...

현재칸을 포함하더라도 2*2사각형이 한계다.

1	1	0
1	2	1
1	2	2

(구멍있는 사각형이 완성됨)

 

그래서 세 값들의 최솟값+1값을 넣으면 된다.

 

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

public class P1915 {

	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][m];

		int result = 0;

		for (int i = 0; i < n; i++) {
			String read = (br.readLine());

			for (int j = 0; j < m; j++) {
				int now = read.charAt(j) - '0';

				if (now == 0) {
					dp[i][j] = 0;
					continue;
				}

				if (i - 1 < 0 || j - 1 < 0) {
					dp[i][j] = 1;
					result = Math.max(result, dp[i][j]);
					continue;
				}

				int left = dp[i][j - 1];
				int up = dp[i - 1][j];
				int up_left = dp[i - 1][j - 1];

				int min = left;
				min = Math.min(min, up);
				min = Math.min(min, up_left);

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

			}
		}

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

}