[ 프로그래머스 ] 가장 큰 정사각형 찾기 ( 자바 )

[ 프로그래머스 ] 가장 큰 정사각형 찾기 ( java )

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

 

핵심 

1. 모든 점을 검사하며, 최대 사각형이 되는지 확인될까?
   O(N^4) 시간초과. dp로 중복처리? 방법이 안 떠오름 
   

2. 계획 단계 수정 - 정사각형을 찾기 위한 새로운 방법, 분해하기 ( DP )
   한 변의 길이 N 정사각형에 N-1 길이의 정사각형이 4가지 다른 위치로 들어갈 수 있다. 말로 설명하기 어렵..
   사각형의 제일 오른쪽 아래 꼭지점에 길이 표시가능하다. 이러한 표시를 보고 특정 위치에서의 사각형을 구할 수 있다. 

아래 블로그에 참조. 그림부터가 설명이 되게 좋다.  

https://blog.sonim1.com/212

배열에서 가장 큰 정사각형 찾기

 

len[y][x] : y, x를 제일 오른쪽 아래 꼭지점으로 하는 정사각형의 변의 길이 

len[y][x] = min( 왼쪽 len, 위 len, 왼쪽 위 대각선 len ) = min( len[y][x-1], len[y-1][x], len[y-1][x-1] )

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

코드

 

class Solution{
	public int solution(int [][]board){
		int up, left, upleft;
		for(int y = 1 ; y < board.length; y++) {
			for(int x = 1 ; x < board[y].length; x++) {
				if(board[y][x] == 1) {
					up = board[y-1][x];
					left = board[y][x-1];
					upleft = board[y-1][x-1];
                    
					int min = Math.min(up, left);
					min = Math.min(min , upleft);
					board[y][x] = min+1;
				}
			}
		}
		
		int ans = 0;
		for(int y = 0 ; y < board.length; y++) {
			for(int x= 0 ; x < board[0].length ; x++) {
				if(board[y][x] > 0) {
					ans = Math.max(ans, board[y][x]);
				}
			}
		}
		return ans*ans;
	}
}