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

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

풀이

 

이 문제는 브루트포스로 푸는 경우 절대 효율성을 통과할 수가 없는 문제입니다.

대충 DP를 써야겠다 라는 생각은 했지만 어떤 방식으로 값을 저장해나갈지 생각할 수가 없어서 질문하기를 보고 풀이했습니다.

 

1. 우선은 표의 모든 숫자가 0으로 이루어져 있는지 확인해야 합니다. 0으로 이루어진 경우 1조차도 될 수 없기 때문입니다.
   • 0으로 이루어진 경우엔 바로 0을 return해 필요없는 연산이 더이상 일어나지 않도록 합니다
2. 이제 본격적으로 가장 큰 정사각형을 찾는 과정입니다. board의 값을 업데이트 시켜나가면서 문제를 해결합니다.
   1. board의 맨윗줄과 맨 오른쪽줄은 어차피 해당 칸보다 큰 정사각형이 만들어질 수 는 없으므로 무시하고 (1, 1)부터 알고리즘을 적용합니다.
   2. 여기서 가장 중요한 식이 board[i][j] = min( board[i-1][j], board[i][j-1], board[i-1][j-1]) 입니다.
   3. 저 식을 적용하면서 answer의 값과 비교할 때 board[i][j]의 값이 더 크다면 answer를 업데이트 해줍니다.
3. 위의 과정을 완료하고 나면 answer에 든 값은 가장 큰 정사각형의 한 변의 길이입니다.
4. 구하고자하는 것은 정사각형의 넓이 이므로 answer를 제곱한 값이 답이 됩니다.

 

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 1;

        int r = board.length;
        int c = board[0].length;
        
        //표가 전부 0으로 이루어진지 확인
        int zero = 0;
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(board[i][j] == 1)
                    break;
                zero++;
            }
        }
        //모두 0인 경우
        if(zero == r*c)
            return 0;
        
        //가장 큰 정사각형 구하기
        for(int i=1; i<r; i++){
            for(int j=1; j<c; j++){
                if(board[i][j] == 0)
                    continue;
                board[i][j] = Math.min(Math.min(board[i-1][j],board[i][j-1]), board[i-1][j-1])+1;
                if(board[i][j] > answer)
                    answer = board[i][j];
            }
        }
        
        //넓이
        answer = answer*answer;

        return answer;
    }
}