문제
접근
DP 문제이다.
왼쪽 위 부터 순서대로 배열을 탐색하며 현재 자리에서 정사각형을 만들수 있는지 판단하면 된다.
판단 기준은 현재 자리가 1일 때, 왼쪽, 위, 왼쪽 위의 값 중 가장 작은 값에 +1을 한다.
가장 작은 값이 0이라면 정사각형은 만들어질 수 없다.
반면 가장 작은 값이 1이상이라면 정사각형이 성립하는 경우이다.
1이라면 현재 위치에서 처음으로 정사각형이 이루어지므로 길이가 2인 정사각형이 된다.
2이상이라면 이미 이전 위치에서 모두 2이상의 정사각형을 이루고 있었으므로, 현재 위치에서 3이상의 정사각형이 이루어진다.
원래 편하게 검사하기 위해서 인덱스를 1부터 탐색했는데,
1 0 0
0 0 0
0 0 0
같은 경우 정답이 1인데 0으로 판단하게 된다.
이러한 예외를 잡으려면 모두 탐색 후 다시 max값을 탐색하는 방법밖에 없어보여서 그냥 0부터 돌며 인덱스 처리작업을 해주었다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
def solution(board):
answer = 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] > 0:
if i > 0 and j > 0:
board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
if answer < board[i][j]:
answer = board[i][j]
return answer*answer