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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

2. 접근 방식

기초적인 DP 문제다. 

다만 주의해야 할 예외사항 2가지가 있다.

 

첫째, 행 또는 열의 길이가 1인 경우. 이 부분의 경우 return 값을 1로 처리했지만 사실 모든 값이 0이라면 0을 반환하는게 맞다. 하지만 테스트 케이스 중에 이 경우가 없는 듯 하다. 즉, 정석적인 방법이라 보긴 힘들듯 하다.

 

둘째, 모든 숫자가 0으로 이루어진 경우다. 초기 값을 0 으로 초기화해주면 해결

 

다른 사람들의 풀이를 보니 행과 열을 1씩 늘려 새로운 배열을 생성해 푸는 방법이 있었다. 

 

3. 구현

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

 

4. 정리