[프로그래머스] 가장 큰 정사각형 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제이다.

정사각형의 넓이를 구하는 문제이므로 한 변의 길이를 구하여 해당 정사각형의 넓이를 구한다.

이 문제를 해결하기 위해 DP 알고리즘을 활용하여 시작 위치부터 마지막 위치까지 탐색하며 해당 위치까지의 가장 큰 정사각형의 한 변의 길이를 저장한다.

그리고 모든 탐색이 끝난 후 가장 긴 변의 길이를 구해 제곱하여 가장 큰 정사각형의 넓이를 구한다.

DP 알고리즘의 결과로 정사각형 변의 길이를 저장할 때 각 위치별 값은 해당 값의 왼쪽, 위쪽, 대각선 위쪽 위치 값 중 가장 작은 값에 1을 더한 결과로 저장한다. 

 

1. 각 위치별 최대 길이를 저장할 2차원 dp 배열을 생성한다. 배열의 크기는 원래 표의 크기보다 각 행과 열을 1씩 늘려 생성한다. dp = list(list(0 for _ in range(len(board[0]) + 1)) for _ in range(len(board) + 1))
2. 가장 긴 변의 길이를 저장할 변수를 생성하고 초기화한다. MAX = 0
3. 모든 위치를 탐색하며 for i in range(1, len(board) + 1): for j in range(1, len(board[0]) + 1)
   1. 해당 위치의 대각선 위의 위치가 1이면 if (board[i - 1][j - 1] == 1)
      1. 해당 dp 배열의 값을 왼쪽, 오른쪽, 대각선 위 위치 중 가장 작은 값을 구하고 구한 값에 1을 더하여 저장한다. dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
      2. 만약 새로 저장한 값이 기존 가장 긴 변의 길이보다 크면 새로 저장한 값을 가장 긴 변의 길이로 저장한다. if (dp[i][j] > MAX): MAX = dp[i][j]
4. 모든 위치를 탐색한 후 구한 가장 긴 변의 길이를 제곱하여 가장 큰 정사각형의 넓이를 구한다. answer = MAX ** 2

3. 소스코드

def solution(board):
    answer = 0

    dp = list(list(0 for _ in range(len(board[0]) + 1)) for _ in range(len(board) + 1))

    MAX = 0
    for i in range(1, len(board) + 1):
        for j in range(1, len(board[0]) + 1):
            if (board[i - 1][j - 1] == 1):
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

                if (dp[i][j] > MAX):
                    MAX = dp[i][j]

    answer = MAX ** 2

    return answer