📜 문제 링크
🔑 풀이
처음엔 그래프 탐색같다고 생각해서 dfs나 bfs를 사용해야 하나 고민했다. 하지만 1인 곳을 탐색할 수는 있어도 그 모양이 정사각형인지를 찾으려면 엄청 복잡할 것 같았다. 전부다 리스트에 넣어놓고 정사각형인지를 하나씩 판별한다던가...
다음으로는 한칸씩 이동하면서 정사각형 모양으로 탐색하는 방식이었다. (0, 0)에서 시작해서 길이가 1인 정사각형, 2인 정사각형을 하나씩 찾아가는 방법인데 가능은 할 거 같았지만(?) 문제는 불필요한 중복이 너무 많이 된다는 거였다. 탐색은 오른쪽 아래로만 이루어지게 되는데, (0, 0)에서 3 길이의 정사각형을 찾으면 (1, 1)에서는 길이가 2인 정사각형을 찾을 수 있게 된다. 1000x1000이라서 중복 연산은 커녕 한 번만 탐색해도 시간 초과일 것 같아서 이 방법도 탈락ㅜ
그 다음에 dp가 떠올랐다. 예전에 백준에서 푼 문제중에 비슷한 문제가 있어서 생각이 났다. 현재 좌표에서 ↖️, ⬆️, ⬅️ 방향이 전부다 0이 아니면 정사각형이 될 수 있다. 이 점을 이용하면 2차원 dp로 가능할 것 같았다. 생각해보면 저 방향에 0이 하나라도 있다면 그 칸은 정사각형이 될 수 없다.
만약에 저 3칸이 전부다 1이상이라면 현재의 칸은 길이가 2인 정사각형이 될 수 있다. 하지만 만약 3칸의 값이 (1, 1, 2)라면? 2칸은 1인 정사각형이지만 1칸은 2인 정사각형의 일부라면? 그런 경우에도 현재의 칸은 길이가 2인 정사각형이 된다. 어차피 길이가 2인 정사각형이 현재의 정사각형과 연결되고 있진 않기 때문이다. 규칙을 생각해보니 3칸의 값 중 가장 작은 값 + 1을 하면 길이 n의 정사각형을 구할 수 있었다.
길이의 제곱을 구해야 하기 때문에 길이를 구한 다음에 한 행씩 비교하면서 최대값을 찾아 제곱값을 리턴
def solution(board):
for i in range(1, len(board)):
for j in range(1, len(board[0])):
if board[i][j]:
board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j])+1
answer = 0
for row in board:
answer = max(answer, max(row))
return answer**2