[Level 2] 가장 큰 정사각형 찾기

programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

---

접근

처음에 완전탐색으로 풀었지만 시간초과가 발생했다.

이후에 다른 사람들의 풀이를 보고 DP로 접근하는 것을 알았다. 하지만 어떻게 DP로 풀어야할지 감이 잡히지 않았다. 

 

내가 이해한 방식은 다음과 같다.

(y, x) 좌표를 기준으로 2x2 크기의 윈도우로 정사각형를 찾아서 크기를 저장해두는 것이다.

1, 1부터 시작을 하여 1이상인 좌표에 대해 왼쪽, 위, 좌상단을 검사하여 최솟값을 찾는다. 만약 이 범위 내에 0이 있다면 정사각형이 아니다. 정사각형이라면 1이상의 정수가 최솟값이 될 것이다. 

최솟값을 찾았다면 +1을 해주는데 탐색을 하면서 정사각형의 크기를 누적해주는 것이다. 

위의 방식으로 진행했을 때 맵 내의 최댓값을 찾아 제곱하여 반환한다.

 

아직까지 DP에 대해 이런식으로 접근하는 것이 익숙하지 않다. 점화식을 세워서 쉽게 풀 수 있는 DP를 제외한 이런 유형의 문제들을 많이 풀어봐야겠다.

 

구현

def solution(board):
    answer = 0
    h = len(board)
    w = len(board[0])
    for y in range(1, h):
        for x in range(1, w):
            if board[y][x] >= 1:
                board[y][x] = min(board[y-1][x-1], board[y-1][x], board[y][x-1]) + 1
    
    answer = max([size for y in board for size in y])**2
    return answer