프로그램어스 Level2 가장 큰 정사각형 찾기 Java

DP(다이나믹 프로그래밍 ) 문제이며 점화식으로 생각하는 연습? botton - up 방식으로 생각하는 연습이 많이 필요할 꺼 같다. 시간초과의 문제가 있기 때문에 단순 반복이나 탐색으로 풀기 힘들기 때문에 -> 뭔가 규칙을 찾거나 DP로 풀 수 밖에 없다는 것은 느꼈지만 해결책을 못 찾앗따. 이럴 때 풀이를 보고 피드백을 받자

package Level2;

import javax.jws.soap.SOAPBinding;

public class 가장큰정사각형찾기 {
	public static void main(String[] args) {
		
		//int board[][] = { {0,1,1,1},{1,1,1,1},{1,1,1,1},{0,0,1,0} };
		int board[][] = { {0,0,1,1},{1,1,1,1}};
		System.out.println(solution(board));
	}
	
	public static int solution(int [][]board)
    {
		//좌측, 좌상단, 상
		int dx[] = {0,  -1, -1}; 
		int dy[] = {-1, -1,  0};
		int N = board.length;
		int answer = 0;
		
		for(int j = 0; j < board[0].length; j++)
			answer = board[0][j];
       
        for(int i = 1; i<board.length; i++) {
        	for(int j =1; j<board[i].length; j++) {
        		
        		if(board[i][j] == 0)
        			continue;
        		
        		int Min_num = 987654321;
        		
        		int number_check = 0;
        		for(int m = 0; m < 3; m++) {
        			int m_x = i + dx[m];
        			int m_y = j + dy[m];
        			if(m_x < 0 || m_y < 0 || m_x > board.length-1 || m_y > board[i].length-1)
        				continue;
        			
        			if(board[m_x][m_y] > 0) {
        				number_check++;
        				Min_num = Math.min(Min_num, board[m_x][m_y]);
        			}
        		}
        		
        		if(number_check == 3) {
        			board[i][j] = Min_num+1;
        			answer = Math.max(board[i][j], answer);
        		}
        	}
        }

        answer *= answer;
        return answer;
    }
}

 

 

참고 블로그 : https://limkydev.tistory.com/133