[백준 / 골드4] 1915 가장 큰 정사각형 (Java)

문제 보기

사용한 것

• 행렬에서 가장 큰 1로 이루어진 정사각형을 찾기 위한 bottom-up

풀이 방법

• 2중 for 문을 돌면서 행렬의 현재 인덱스의 값이 1인 경우 dp[i][j]는 다음 중 최소와 같다.
  • dp[i - 1][j] + 1
  • dp[i][j - 1] + 1
  • dp[i - 1][j - 1] + 1
• 이번 인덱스를 포함해서 정사각형을 만족하려면, 위 세개도 모두 정사각형으로 같은 값이기 때문이다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] dArr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            line = br.readLine();
            for (int j = 1; j <= m; j++) {
                dArr[i][j] = line.charAt(j - 1) - '0';
            }
        }

        // DP
        int answer = 0;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dArr[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    answer = Math.max(dp[i][j], answer);
                }
            }
        }

        System.out.println((int) Math.pow(answer, 2));
    }
}