[Level 2] 가장 큰 정사각형

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

 

def solution(b):
    len_x = len(b)
    len_y = len(b[0])
    
    for x in range(1, len_x):
        for y in range(1, len_y):
            if b[x][y] == 1:
                b[x][y] = min(b[x][y-1], b[x-1][y], b[x-1][y-1])+1
            
    return(max([i for x in b for i in x])**2)

 

▷ 이 문제의 가장 핵심은 DP(Dyanamic Programming)을 이용하여 푸는 것이다. DP를 이용하지 않을 경우, 시간이 초과되는 문제가 발생한다. 따라서 정사각형의 모든 지역을 탐색하되, 탐색된 해당 지역의 정보를 다음 탐색에 활용하는 DP를 통해 시간을 줄여야 한다.

 

▷ 탐색 지점 b[x][y]가 1인 경우, b[x][y-1], b[x-1,y], b[x-1][y-1]의 최소값에 1을 더하여 다음 탐색 지점에 이 정보를 전달한다. 이 과정을 마친 후, 가장 최대가 되는 b[x][y]를 찾고, 이 값의 제곱을 정답으로 출력한다.