프로그래머스 가장 큰 정사각형 찾기

1. 프로그래머스 가장 큰 정사각형 찾기

1.1. 컴퓨팅적 사고

1. 보드에서 0인 경우를 제외한다. 0인 경우에는 어떠한 정사각형도 만들 수가 없기때문이다.
2. 따라서, 대각선(i-1,j-1), 위(i-1,j), 왼쪽(i,j-1)의 위치의 값중 최솟값 +1의 값을 주게해주는데 왜 이러한 값을 구해주는 것일까 잘 생각해보도록 합니다.
3. 가장 최소가되는 값의 +1의 값으로 진행하면 하나의 정사각형의 최대 변의 길이를 구할 수 있게 되기 때문입니다.
   이러한식으로 점화식을 도출해내면
   Math.min(map[i-1][j-1]+1, Math.min(map[i-1][j], map[i][j-1]))+1
4. 다음과 같이 구할 수 있게 됩니다.
   결국 우리가 구한값은 가장 큰 정사각형의 변의 길이를 구한것 이므로 해당되는 변의 길이 * 변의 길이 = 넓이를 도출해낼 수 있습니다.

1.2. 소스코드

public class 가장큰정사각형찾기 {
    public static void main(String[] args) {
        solution(new int[][]{{0,1,1,1},{1,1,1,1},{1,1,1,1},{0,0,1,0}});
    }

    static int solution(int[][] board) {
        int answer = 0;
        int[][] map = new int[board.length+1][board[0].length+1];
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                map[i+1][j+1] = board[i][j];
            }
        }
        for(int i=1; i<=board.length; i++){
            for(int j=1; j<=board[0].length; j++){
                if(map[i][j] != 0){
                    // 가장 최솟값의 + 1 괄호 주의 !
                    map[i][j] = Math.min(Math.min(map[i-1][j], map[i][j-1]), map[i-1][j-1])+1;
                    answer = Math.max(answer, map[i][j]);
                }
            }
        }
        System.out.println(answer);
        return answer*answer;
    }
}