[프로그래머스] Level2, 가장 큰 정사각형 찾기 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/12905?language=python3 

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

 

코드

def solution(board):
    answer = 0
    for i in range(1,len(board)):
        for j in range(1, len(board[0])):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
    return max([j for i in board for j in i])**2

DP를 이용하여 정사각형 변의 길이를 누적해서 리스트에 넣은다음에 가장 큰 수를 찾아 넓이를 구하면 된다.

0번째 행과열은 누적하기 위해서 기본 값으로 두고 1부터 시작한다.

 

board[i][j]가 1인 경우 왼쪽, 위쪽, 대각선 위쪽을 확인하여 가장 작은 값에 +1을 해준값을 board[i][j]에 채워준다.

min으로 해주는 이유는 한개라도 0이거나 다른 수 보다 작다면 정사각형이 아니기 때문에 min을 이용해 구해준다.

 

0 1 1 1                 

1 1 1 1      

1 1 1 1

0 0 1 0

 

board[1][1]부터 확인한다 board[0][0]이 0으로 최솟값이므로 +1 한 값인 1이 board[1][1]에 들어간다.

다음으로 board[1][2]는 왼쪽, 대각선 위쪽, 위쪽 모두 1이므로 +1 한 2값이 들어가게 되어서 변의 길이가 2인 정사각형을 만들 수 있게 된다.

 

쭉쭉 하다보면 ...

 

0 1 1 1

1 1 2 2

1 2 2 3

0 1 2 3

 

이런식으로 되어서 최대 변의길이가 3인 정사각형을 만들수 있게 된다.

 

그리고 return에 for문은 2중 for문 돈 뒤에 리스트에 append하는 과정을 축약 해놓은 것이다.