📖문제

📝풀이과정

board의 최대 크기가 1000 x 1000이기 때문에 완전 탐색으로 했다가는 시간초과가 난다. 따라서 다이나믹 프로그래밍으로 문제를 푼다.

• 만약 주어진 board의 행이나 열의 길이가 2 미만인 경우에는 board에 1이 있는지 확인한다.
  1이 있다면 가장 큰 정사각형의 크기는 1이므로 1을 리턴하고, 없다면 정사각형이 존재하지 않으므로 0을 리턴한다.
• board의 (1,1)부터 시작하여 다음 과정으로 가장 큰 정사각형을 구한다. 현재 위치를 (i, j)라 하자.
  1. board의 (i, j)위치에 있는 값이 1이라면 (i-1, j-1): 왼쪽위, (i, j-1): 위, (i-1, j-1): 아래 위치에 있는 값을 확인한다.
  2. 1번의 세가지 위치에 있는 값들중 최솟값을 구한다.
  3. board의 (i, j) 위치의 값을 (2번에서 구한 최솟값 + 1)으로 갱신한다.

     즉, board의 (i, j) 위치의 값은 (i, j)를 오른쪽 아랫점으로 가지는 정사각형의 변의 길이 중 최댓값이 된다.

  4. 현재까지 구한 정사각형의 변의 길이의 최댓값보다 3번에서 구한 값이 크면 answer도 3번에서 구한 값으로 갱신한다.
• 그림으로 설명하기

1. (0, 0)인 경우
   
2. (2, 3)인 경우
   
3. 최종
   

⌨코드

def solution(board):
    
    row = len(board)
    column = len(board[0])

    if row < 2 or column < 2:
        for r in board:
            if 1 in r:
                return 1
        return 0
        
    answer = 0
    for i in range(1, row):
        for j in range(1, column):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1
                answer = max(answer, board[i][j])

    return answer**2

😊 느낀점

DP로 풀 수 있을 줄은 정말 꿈에도 상상 못했다....
완전 탐색은 아니라는 걸 직감적으로 느꼈지만 다른 방도를 못 구하겠어서 구글링의 힘을 빌렸다🤔 어떻게 이런 생각들을 하시는 거지...ㅜㅜ
오늘 하루 종일 고민했어도 이런 풀이 방법은 생각 못했을 것 같아서 너무 감명받아서 이건 꼭 기록해야겠어서 블로그를 썼다...