프로그래머스 / lv2 / 가장 큰 정사각형 찾기

문제

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이다. 

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

======================================================================================================

 

제한사항

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

 

입출력 예

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

해결

이 문제는 동적 프로그래밍으로 해결할 수 있다. 최소 크기인 2*2 정사각형과 3*3 정사각형일 경우를 생각해서 규칙을 만들었다.

결국 어떤 위치에 1이 있을 경우, min(arr[i-1][j], arr[i][j-1], arr[i-1][j-1]) + 1을 하면 된다.

코드

 

느낀점

이 문제를 풀기 전에는 동적 프로그래밍에 대해 알지 못했는데, 막혀서 찾아보니 이 방법을 이용해야 풀 수 있었다. 그래서 동적 프로그래밍에 대해서 공부를 한 후에 다시 코드를 분석하고 이해할 수 있었다.

 

출처

https://youjourney.tistory.com/100

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