2022년 05월 13일 프로그래머스 - 가장 큰 정사각형(다이나믹 프로그래밍, DP)

 

 

 

import java.util.*;


class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        
        //초기값 상정을 위한 row, col 변수 설정
        int row = board.length;
        int col = board[0].length;
        
        //초기값 : 만약 행, 열의 길이가 1일 경우, 1리턴
        if(row < 2 || col < 2) return 1;

        
        //최솟값 미리 선언
        int min = 0;
        
        
        //초기값이 아닌 경우의 DP 로직
        for(int i=1; i<row; i++)
        {
            for(int j=1; j<col; j++)
            {
                //만약 현재 위치의 값이 1이 아닐경우
                if(board[i][j]==1)
                {
                    //왼쪽상단(↖︎), 위쪽(↑), 왼쪽(←) 중 최솟값
                    //JAVA에서 Min 함수는 두개씩밖에 비교불가 - 안에 다시 사용했음
                    min = Math.min(board[i-1][j], Math.min(board[i][j-1], board[i-1][j-1]));
                        
                    //자신의 값에 그 최솟값+1
                    board[i][j] = min+1;
                }
                
                
                //할당된 값들 중 최댓값을 answer에 할당
                if(answer < board[i][j]) answer=board[i][j];
            }
        }
        
        return answer*answer;
    }
}

 

 

 

※ 참고자료

 

https://onlydev.tistory.com/65

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

 

 

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)