[Programmers] 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

난이도: level 2

정답률: 38% (2024.07.31 기준)

완료한 사람: 6359명 (2024.07.31 기준)

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

이 글에서는 주어진 2D 배열 board에서 1로 구성된 가장 큰 정사각형의 넓이를 찾는 방법을 설명합니다. 이 문제는 동적 계획법(Dynamic Programming)을 이용하여 효율적으로 해결할 수 있습니다. 아래는 Python으로 작성된 해결 코드와 그에 대한 상세한 설명입니다.

 

코드구현

def solution(board):
    answer = board[0][0]
    row, col = len(board[0]), len(board)
    
    for c in range(1, col):
        for r in range(1, row):
            if board[c][r] == 1:
                board[c][r] = min(board[c-1][r-1], board[c][r-1], board[c-1][r]) + 1
                answer = max(answer, (board[c][r])**2)

    return answer

 

코드 설명

 

초기화

• answer 변수는 board의 첫 번째 값을 초기값으로 설정합니다. 이는 board가 비어 있지 않다는 가정 하에 가능합니다.
• row와 col 변수는 각각 board의 행과 열의 길이를 나타냅니다.

2D 배열 순회

• 이중 for 루프를 사용하여 배열의 모든 원소를 순회합니다. 여기서 c는 열을, r는 행을 나타냅니다. 인덱스는 1부터 시작하여 첫 번째 행과 첫 번째 열은 건너뜁니다.

동적 계획법 적용

• 현재 원소가 1인 경우, 즉 board[c][r] == 1일 때, 해당 위치가 정사각형의 일부가 될 수 있습니다.
• 이 위치의 값을 이전 위치들 (board[c-1][r-1], board[c][r-1], board[c-1][r])의 최솟값에 1을 더한 값으로 업데이트합니다. 이는 현재 위치를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이를 나타냅니다.
• 예를 들어, 이전 위치들 중 가장 작은 값이 2라면 현재 위치는 2x2 정사각형의 연장선이므로 3으로 업데이트됩니다.
• 이 값을 제곱하여 현재까지 발견된 최대 정사각형의 넓이와 비교하여 answer를 업데이트합니다.

결과 반환

• 최종적으로 answer는 1로 구성된 가장 큰 정사각형의 넓이를 나타내며, 이를 반환합니다.

최종 결과

 

 

연습 예시)

input = [[0, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1]]
input = 
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 1

answer = 16
final = 
0 0 0 1 1 1
0 0 0 1 2 2
1 1 1 1 2 3
1 2 2 2 2 3
1 2 3 3 3 3
0 1 2 3 4 4