[Python] 프로그래머스 Lv.02 - 가장 큰 정사각형 찾기

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

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

[ 알고리즘 ]

구현

 

[문제 접근]

언뜻보면 완전 탐색으로 구현할 수도 있는 문제지만, 그렇게 구현하면 엄청나게 복잡한 코드가 탄생할 것 이다.

표가 0,1로만 이루어져있다는 점과, 정사각형이라는 점을 이용하여 머리를 굴려야했던 문제이다

위,아래,왼쪽 대각선 중에 가장 최솟값을 자신에게 더해 나간다. 그렇게 되면 2로 이루어진 3개는 겹쳐서 2*2의 정사각형이 존재한다는 의미이므로 해당 표의 숫자가 1 이면 1+2로 한 변의 길이가 3인 정사각형을 보장할 수 있을 것이다

 

이때 주의해야할 점은 해당 숫자가 0이면 그 부분은 이미 정사각형이 만들어지지 않으므로 제외시켜야한다.

 

[코드]

def solution(board):
    answer=0
    
    x=len(board)
    y=len(board[0])
    
    if x==1 and 1 in board:
        answer=1
    
    for i in range(1,x):
        for j in range(1,y):
            Min=min(board[i][j-1],board[i-1][j],board[i-1][j-1])
            
            if Min!=0 and board[i][j]!=0:
                board[i][j]+=Min       
    result=[]
    for i in range(x):
        result.append(max(board[i]))
    answer=max(result)
    
    return answer**2