[알고리즘] 프로그래머스 - 가장 큰 정사각형 찾기 ( 레벨2 - DP )

프로그래머스 레벨2 문제 중 '숫자의 표현'이라는 문제입니다. DP 기본 문제입니다.

• 문제 출처 : 링크
• DP
• 관련 문제 : 프로그래머스 땅따먹기 

---

풀이 포인트

• 0과 1로만 배열이 되어있기 때문에 정사각형이 되는 지점에서 최대값을 메모라이제이션을 하면됩니다.
• 정사각형이 되는 지점을 찾는 것은 정사각형에서 오른쪽 아래를 기준으로 위, 왼쪽, 대각선이 모두 1이면 정사각형이라고 판단하면 됩니다.
• 위 내용을 기준으로 전체를 탐색합니다.
• 배열의 위치값이 1이면 해당 값을 기준으로 정사각형을 판단하고, 해당 위치의 메모라이제이션 값은 원래 board의 값으로 추출하는 것이 아니라, 메모라이제이션 배열에서 정사각형에 포함되는 값들 중 가장 작은 값 +1을 해주면 됩니다.
• 위 로직대로 동작하면 위 그림처럼 값이 채워지게되는데, 그 값중 최대값이 정답입니다.

class Solution{
    public int solution(int [][]board){
        int answer = 0;
        int [][]arr = new int[board.length+1][board[0].length+1];
        for(int i = 1; i <= board.length; i++) {
            for(int j = 1; j <= board[0].length; j++){
                if(board[i-1][j-1] != 0) {
                    int min = Math.min( Math.min(arr[i-1][j], arr[i][j-1]), arr[i-1][j-1]  );
                    arr[i][j] = min+1;
                    answer = Math.max(answer, min + 1);
                }
            }
        }
        answer *= answer;
        return answer;
    }
}

 

연관문제

2차원 배열에서 DP를 활용하여 문제를 풀이하는 문제로는 프로그래머스 땅따먹기 문제가 있습니다.