[프로그래머스] 가장 큰 정사각형

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

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

 

문제 설명

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

정답은 9

 

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

풀이과정

정사각형의 크기를 누적해 나가면서 x, y에서 정사각형이 되는 (x - 1, y) , (x , y - 1), (x -1 , y - 1)의 최솟값에 +1 을 하면 정사각형의 크기를 구 할 수 있다.

 

소스코드

function solution(board)
{
	var answer = 0;
	var dp = new Array(board.length);
	for (var i = 0; i < dp.length; i++) {
		dp[i] = new Array(board[i].length);
		dp[i].fill(0);
	}
	function checkBoard(x, y) {
		var min = 999;
		var dx = [-1, -1 ,0];
		var dy = [0, -1, -1];
		for (var i = 0; i < 3; i++) {
			var cx = dx[i] + x;
			var cy = dy[i] + y;
			if (cx < 0 || cy < 0 || cx >= board[0].length || cy >= board.length) continue;
			if (min > dp[cy][cx]) {
				min = dp[cy][cx];
			}
		}
		return min + 1;
		
	}
	for (var i = 0 ; i < board.length; i++) {
		for (var j = 0; j < board[0].length; j++) {
			if (j == 0 || i == 0) {
				dp[i][j] = board[i][j];
			}
			else {
				dp[i][j] = board[i][j] === 0 ? 0 : checkBoard(j, i);
			}
			if (dp[i][j] > answer) {
				answer = dp[i][j];
			} 
		}
	}
	return answer * answer;
}