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

 


1. 문제

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

2. 풀이

  • dp를 이용하여 문제를 해결해야 합니다.
  • dp_map에 현재 인덱스에서 가능한 최대 정사각형의 크기를 기록해놓습니다.
    • 각 칸을 모두 돌면서 왼쪽, 위, 왼쪽 대각선 위를 살펴보고 해당 값에서 가장 작은 값 + 1로 갱신합니다.
    • 이는 직접 그려보면서 이해하면 더 쉬운데, k 크기의 정사각형을 현재 위치에서 만들기 위해서는 위의 3개의 위치에서 k-1 이상의 값을 가져야 하기 때문입니다.
k - 1 k - 1
k - 1 k
def solution(board):
    answer = 0
    row = len(board)
    col = len(board[0])
    dp_map = [[0] * col for _ in range(row)]
    
    for i in range(0, row):     # 하나라도 1이 있는지 확인합니다.
        for j in range(0, col):
            if board[i][j] == 1:
                answer = 1
                break
                
    for i in range(row):            # 첫 행과 첫 열은 board에 있는 값과 동일하게 넣어줍니다. 
        dp_map[i][0] = board[i][0]
    for i in range(col):
        dp_map[0][i] = board[0][i]

    for i in range(1, row):         # dp를 이용하여 문제를 해결합니다.(아래의 설명을 따라 그림을 그려보면 이해가 쉽습니다)
        for j in range(1, col):     # 모든 칸을 돌면서 board의 값이 1인 경우에는 dp_map 갱신을
            if board[i][j] == 0:    # 왼쪽, 위, 왼쪽 대각선 위를 살펴보고 해당 값에서 가장 작은 값 + 1로 갱신합니다.     
                dp_map[i][j] = 0    # dp_map에는 해당 위치에서 가능한 직사각형의 크기를 저장합니다. 
            else:                   # k 크기의 정사각형을 현재 위치에서 만들기 위해서는 위의 3개의 위치에서 k-1 이상의 값을 가져야 합니다. 
                dp_map[i][j] = min(dp_map[i - 1][j - 1], dp_map[i - 1][j], dp_map[i][j - 1]) + 1
                answer = max(answer, dp_map[i][j])

    return answer*answer