221. Maximal Square / leetCode

문제링크 : https://leetcode.com/problems/maximal-square/
Submission : https://leetcode.com/submissions/detail/298397463/
Java Source : https://github.com/skysign/WSAPT/blob/master/LeetCode/221.%20Maximal%20Square/src/Main.java

정사각형의 면적을 구하는 문제입니다. 코딩은 Recursive call을 사용해서, 사각형의 면적을 계산하는 방식을 사용해서 풀었습니다.

1. 이중루프를 사용해서, 모든 위치를 방문해서, '1' 인 위치를 찾습니다.
2. Recursive call을 사용해서, 사각형의 면적을 테두리 부분만 1인지 확인합니다.

이중 루프를 순서대로 돌면서, '1'인 위치를 찾습니다.
위의 그림과 같다면, (1,1)을 찾고 adj1() 메서드를 콜하게 되고, 이후 2번 더, Recursive call을 하게 됩니다.

• d=0인 adj1() 메서드를 콜하게 되고, 파란색부분이 1인지 확인하게 되고, 1^2 면적 1
• d=1인 adj1() 메서드를 콜하게 되고, 주황색부분이 1인지 확인하게 되고, 2^2 면적 4
• d=2인 adj1() 메서드를 콜하게 되고, 연두색부분이 1인지 확인하게 되고, 2^2 면적 9

이렇게 구현하면, 1인 정사각형의 크기가 더 커지더라도, 한번 1인지 확인한 셀은 2번 확인하지 않도록 코딩할 수 있습니다.

추가적으로 최적화할 수 있는 방법이 있습니다. 아래에 자바 소스에 코딩은 하지 않았지만, 한번 1로 이루어진 사각형을 찾으면, 사각형의 크기에 따라서, 방문하지 않아도 되는 셀이 생기게 됩니다.
위의 그림 대로 라면, (1,1)을 방문하고, 3x3 크기의 사각형이 있는 것을 찾았으므로, (1,2) 부터 이후 셀은 방문할 필요가 없습니다. 왜냐하면, 맵의 크기가 5x5이고, 이미 찾은 사각형의 크기는 3x3입니다.
따라서, 다른 셀을 방문해봐도, 이미 찾은 3x3 크기의 사각형보다 큰 사각형을 찾을 수 는 없습니다.

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    public void solve() {
//      char[][] map = new char[][]{
//        {'1','1','1','1'},
//        {'1','1','1','1'},
//        {'1','1','1','1'}};
        char[][] map = new char[][]{
                {'0','0','0','1'},
                {'1','1','0','1'},
                {'1','1','1','1'},
                {'0','1','1','1'},
                {'0','1','1','1'}};
        int r = maximalSquare(map);
        System.out.println(r);
    }

    public int maximalSquare(char[][] matrix) {
        int r = 0;

        for(int i=0; i<matrix.length; ++i) {
            for(int j=0; j<matrix[0].length; ++j) {
                if('1' == matrix[i][j])
                    r = Math.max(r, adj1(matrix, i, j, 0, matrix.length, matrix[0].length));
            }
        }

        return r;
    }

    public int adj1(char[][] map, int i, int j, int d, int M, int N) {
        if(!((i+d)<M))
            return 0;

        if(!((j+d)<N))
            return 0;

        int I = i +d;
        int J = j +d;
        boolean br = true;

        for(int tj=j; tj<J; ++tj) {
            br &= (map[I][tj] == '1');
            if(!br)
                return 0;
        }

        for(int ti=i; ti<I; ++ti) {
            br &= (map[ti][J] == '1');
            if(!br)
                return 0;
        }

        if('1' != map[I][J])
            return 0;

        int r = (int)Math.pow(d+1, 2);

        return Math.max(r, adj1(map, i, j, d+1, M, N));
    }
}