BOJ) 가장 큰 정사각형

가장 큰 정사각형

1915번: 가장 큰 정사각형

풀이

 

전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다.

당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다.

 

우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다.

세 곳의 최소값 +1(자기자신)이 dp의 값이 된다.

dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다.

변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다.

(손으로 위의 식을 풀어가다보면 쉽게 이해할 수 있다)

 

위에서 값을 갱신하면서, 최대값 또한 갱신한다. (답을 찾기 위해)최장 길이 ^2이 답이 된다.

 

 

코드

 

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

public class Main {
    static int[] dx = {-1,-1,0}, dy = {-1,0,-1};

    final static int ZERO_Character = '0', ZERO = 0;

    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()), m = Integer.parseInt(st.nextToken());
        int[][] map = new int[n+1][m+1];

        for(int i=1; i<=n; i++) {
            char[] inputArr = br.readLine().toCharArray();
            for(int j=1; j<=m; j++) {
                map[i][j] = inputArr[j-1] - ZERO_Character;
            }
        }
        br.close();
        solution(n,m,map);
    }

    private static void solution(int n, int m, int[][] map) {
        int max = 0;
        for(int y=1; y<=n; y++) {
            for(int x=1; x<=m; x++) {
                if(map[y][x] != ZERO) {
                    int min = Integer.MAX_VALUE;
                    for (int i = 0; i < 3; i++) {
                        int nx = x + dx[i], ny = y + dy[i];
                        min = Math.min(map[ny][nx], min);
                    }
                    map[y][x] += min;
                    max = Math.max(max, map[y][x]);
                }
            }
        }
        System.out.println(max*max);
    }
}