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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

문제 설명

1와 0으로 채워진 표를 이용해 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return하는 문제이다.

제한사항

• 표는 2차원 배열로 주어집니다.
• 표의 행의 크기 : 1,000 이하의 자연수
• 표의 열의 크기 : 1,000 이하의 자연수
• 표의 값은 1 또는 0으로만 이루어져 있습니다.

 

풀이

dp를 활용한 문제이다.

정사각형의 최대 넓이를 알기 위해선 최대 길이를 알아야 하는데, 첫 행과 첫 열을 제외하고,

1의 값을 가진 (x, y)를 각각 위, 왼쪽, 왼쪽 대각선의 최소값에 1을 더하여 찾을 수 있다.

 

만약 아래와 같이 표가 1로 채워져 있다면, (2, 2)는 2로 바뀌면서 최대 길이가 2가 된다. 

 

 

아래와 같은 표가 주어졌다면 왼쪽 대각선의 값이 0이므로, (2, 2)는 1이 되어 최대 길이는 1이 된다. 

 

이와 같이 표에 주어진 값에 따라 dp 리스트를 갱신해가면서 리스트의 최대값을 구하여 제곱을 하면 값을 구할 수 있다.

 

문제에 주어진 표를 예시로 들어보면,

 

위의 dp 리스트에서 최대값은 3이 되고, 최대 넓이는 최대길이의 제곱인 9를 return하면 문제를 풀 수 있다.

 

✅ Code - 성공

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