[프로그래머스/PYTHON] 가장 큰 정사각형 찾기

프로그래머스 '가장 큰 정사각형 찾기' 문제 풀이입니다.

 

문제 링크

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

 

● 문제 간단 설명

주어진 2차원 배열에 대해서 4개의 영역으로 나누었을 때 한 영역 내부에 요소가 모두 1이거나 0일 경우 그 영역을 1이나 0으로 치환한다. 4개의 영역의 크기가 1이 될 때까지 나누는 과정과 치환하는 과정을 반복한다고 할 때 반복이 모두 끝났을 때 0과 1의 개수를 구하는 문제.

 

● 문제 해결 방향

우선 무작정 완전 탐색을 활용할 수 밖에 없었다.

row, col 의 길이중 짧은 길이를 maxLength로 두고 점점 사이즈를 줄여나가면서 row, col에서 직사각형을 발견했을 때 결과 값을 Return하도록 하였다.

 

하지만 이 문제는 동적계획법의 의도에 따라서 작은 정사각형( 작은 문제 )를 가지고 큰 정사각형 ( 큰 문제 )까지 점점 쌓아가며 문제를 해결해야하기 때문에 동적계획법을 사용하지 않으면 효율성 부분을 패스하기 힘들 것이라 생각한다.

 

● 문제 해결 코드

def solution(board):
    answer = 0
    rowLen = len(board)
    colLen = len(board[0])
    
    limitSize = rowLen if rowLen < colLen else colLen
    
    for size in range(limitSize, 0, -1):
        
        for startRowIndex in range(rowLen - size + 1):
            for startColIndex in range(colLen - size + 1):
                arr = []
                for rowData in board[startRowIndex : startRowIndex + size]:
                    arr += rowData[startColIndex : startColIndex + size]
                
                # print(arr)
                if 0 not in arr:
                    return sum(arr)

    return 0;

처음 작성한 코드다.

나의 무지 덕분에 4중 for문이라는 끔찍한 로직이 작성되었다.

정확성 부분에서는 모두 통과했지만, 효율성 부분도 체크하는 문제라 당연히 빨간불이 잔뜩 나왔다.

 

엉터리 코드지만 잠깐 설명하면

완전 탐색을 통해서 정사각형 크기에 따라서 row, col을 모두 지나오면서 정사각형을 발견하면 그 제곱수를 return 하는 로직이다.

 

현재 코드에서 효율성을 통과하려고 노력을 했으나...  양심도 없지...

통과할 수 가 없어서 다른 풀이를 참고하여 다음 같은 로직을 완성하였다.

def solution(board):
    answer = 0
    rowLen = len(board)
    colLen = len(board[0])

    dpArr = [[0] * colLen for i in range(rowLen)]

    for row in range(rowLen):
        for col in range(colLen):

            if row == 0 or col == 0:
                dpArr[row][col] = board[row][col]

            else:
                if board[row][col] == 0:
                    dpArr[row][col] == 0
                else :
                    dpArr[row][col] = min(dpArr[row - 1][col], dpArr[row][col - 1], dpArr[row-1][col - 1]) + 1

    for result in dpArr:
        maxValue = max(result)
        if answer < maxValue:
            answer = maxValue
    
    return answer ** 2

동적 계획법(Dynamic Programming)을 활용하여 현재 위치에서 가능한 정사각형의 변의 길이를 낮은 인덱스에서부터 높은 인덱스로 점점 쌓아가면서 변의 길이를 구해나간다.

 

동적 계획법으로 만들어낸 각 위치에서 생성할 수 있는 가장 큰 변의 길이를 담고있는 매트릭스에서

가장 큰 값의 제곱 수를 return 하도록 하였다.

 

전에 동적계획법에 대한 내용을 한번 정리하긴 했는데,

문제에 대해서 바로바로 적용시키진 못한 것 같다.

 

● 참고

[알고리즘] 동적 계획법 (Dynamic Programming)