[문제 바로가기] 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
가 있다면 가장 큰 정사각형은0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.제한사항 )
표(board)는 2차원 배열로 주어집니다.
표(board)의 행(row)의 크기 : 1,000 이하의 자연수
표(board)의 열(column)의 크기 : 1,000 이하의 자연수
표(board)의 값은 1또는 0으로만 이루어져 있습니다.입출력 예 )
입출력 예 #1
board : [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]
answer : 9입출력 예 #2
board : [[0,0,1,1],[1,1,1,1]]
answer : 4입출력 예 설명 )
입출력 예 #1
위의 예시와 같습니다.입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.
💡 문제 풀이
처음엔, 나올 수 있는 정사각형 면적의 최대값부터 점차 줄여나가면서
반복문을 사용한 완전탐색으로 찾을까 했지만 제한사항에서 알려준 행, 열의 최대값이 1000이므로 포기(by 시간복잡도)
이후 정사각형은 좌우 길이가 같다는 특징을 생각하여 대각선 원소에 접근하였고
정사각형의 최소단위부터 최대로 확장할 수 있는 정사각형의 값을 찾고자했다.
단, 1x1은 자기 자신이 정사각형이므로 의미가 없어 다음으로 최소 단위인 2x2 정사각형을 기준으로 했다.
ex1)
1 1
1 1 은 정사각형이 될 수 있는 후보이다.
1 1
1 2 후보가 될 수 있는 정사각형(2x2)의 우측아래 원소는 자신을 제외한 3개의 값의 최소값+1을 해준다.
ex2)
1 1 1
1 1 1
1 1 1 역시 3x3 정사각형이며 2x2 단위로 반복하게 되면
1 1 1
1 2 2
1 2 3 처럼 표현할 수 있다.
※ 최소값+1을 해주는 이유는 나머지 원소들이 정사각형으로 더 확장할 수 있는지를 점검하기 위함이다.
cf)
1 1 1
1 1 1 의 경우
1 1 1
1 2 2 로 표현하여 2x2가 최대 정사각형임을 알 수 있다.
정리해보면...
step1)
반복문을 이용하여 가장 작은 정사각형 단위(2x2)로 board를 탐색
step2)
모든 원소가 1보다 크면(= 정사각형 후보) 우측 아래 끝 원소의 값을 나머지 3개 원소의 최소값 + 1로 최신화
※ 우측 아래 끝 원소 값을 바꾸기 때문에 행, 열 범위는 모두 1부터 len(board)까지다.
step3)
만약 우측 아래 끝 원소의 값이 answer 보다 크면 answer값 최신화
step4)
answer 값이 곧 정사각형의 길이이므로 제곱(**2)하여 return
...
위 4단계만 구현하였더니 테스트케이스 2개가 오답이었다...
[[0], [0]]] 또는 [[1], [0]]과 같은 상황을 고려하지 않았다
따라서 step0이 필요!
step0)
board를 행 단위로 먼저 탐색했을 때
if : 단 하나의 '1'이라도 나오면 가능한 정답의 최소값은 1이므로 answer = 1
else : 모든 원소가 0이면 정답은 무조건 0
제출한 코드는 다음과 같다.
def solution(board):
for row in board: # 정답의 최소값이 0인지 1인지 먼저 판별
if sum(row):
answer = 1
break
else:
return 0
# 1행 1열부터 board를 2x2 정사각형으로 탐색하면서 우측 아래 값 최신화
for i in range(1, len(board)): # 행
for j in range(1, len(board[0])): # 열
if board[i-1][j-1] and board[i-1][j] and board[i][j-1] and board[i][j]:
board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
answer = max(answer, board[i][j])
return answer ** 2