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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

 

2. 입력

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

 

3. 예제

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

 

4. 풀이

가장 작은 정사각형은 2차원 배열의 값이 1이 되면 길이가 1인 정사각형이 됩니다.

그럼 4칸의 정사각형이 되는지 여부는 어떻게 알 수 있을까요?

1	1
1	현재위치

위 표에서 현재 위치에서 좌측과, 상단, 그리고 11시 방향의 대각선 이 모두 1인 경우 길이가 2인 정사각형이 됩니다.

만약 한 곳이라도 1이 아니라면 해당 사각형은 정사각형이 되지 못합니다.

이번에는 9칸의 정사각형이 되는지 여부는 어떻게 알 수 있을까요?

위 표에서 현재 위치에서 좌측과, 상단, 그리고 11시 방향의 대각선이 모두 1인 경우이면서 또한 각각의 좌측, 상단, 11시 방향의 대각선이 모두 1인 경우가 길이가 3인 정사각형이 됩니다.

 

이런 방법으로 만약 문제를 풀게 된다면 큰 정사각형을 확인하려면 많은 시간이 소요될 것입니다.

그래서 DP를 이용하여 이전 정사각형 여부를 확인한 결과를 표시하여 추가적으로 이전 정사각형에 대한 여부 확인 과정을 생략하도록 하겠습니다.

 

DP를 이용하기 위해 위에서 4칸으로 정사각형을 확인 한 방법처럼 9칸의 정사각형을 4칸의 정사각형으로 나누어 생각해보겠습니다.

 

각각의 4칸의 정사각형은 3곳의 값이 모두 1이기에 2가 될 수 있는 것이며 만약 한 곳이라도 1이 되지 못한다면 2가 될 수 없어 1일 될 것입니다.

이 말은 3곳의 값들 중 가장 작은 값보다 1만큼 큰 값이 현재 위치의 값이 된다는 말과 동일합니다.

 

그러므로 현재 위치의 값은 Min(현재 위치의 왼쪽의 값, 현재위치의 상단의 값, 현재위치의 11시 대각선의 값) + 1이 될 것입니다.

 

위 그림의 9칸의 정사각형을 확인하겠습니다.

 

9칸의 경우는 이미 4칸씩 나누어 이전에 값들을 모두 확인하였으므로 현재 위치에서 좌측, 상단, 11시 대각선의 값들 중 가장 작은 값에 + 1을 한 값이 되므로 3이 됩니다.

 

문제는 정사각형의 최대 넓이를 구하는 것으로 입력으로 주어진 2차원 배열을 순회하면서 만들어질 수 있는 정사각형의 길이를 구한 뒤 길이 * 길이의 값을 Max에 담아 최종 가장 넓은 정사각형을 찾아 반환합니다.

 

5. 코드

전체 코드는 Git에 있습니다.

int[][] map = new int[board.length + 1][board[0].length + 1];

int maxLen = 0;
for (int i = 1; i <= board.length; i++) {
	for (int j = 1; j <= board[0].length; j++) {
		if(board[i-1][j-1] != 0) {
			int min = Math.min(Math.min(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1]);
			map[i][j] = min + 1;

			maxLen = Math.max(maxLen, min + 1);
		}
	}
}

return maxLen * maxLen;