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

문제 설명

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

 

예를 들어

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

 

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

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

---

입 출력

입출력

---

풀이

def solution(board):
    width = len(board[0])
    height = len(board)
    for x in range(1,height):
        for y in range(1,width):
            if board[x][y] == 1:
                board[x][y] = min(board[x-1][y-1],min(board[x-1][y],board[x][y-1]))+1
    
    return max([item for row in board for item in row])**2

결과

---

코드 풀이

부분 탐색으로 풀면 효율성에서 떨어지기 때문에 Dp를 활용해서 풀어야 한다.

프로그래머스에서 제공하는 강의가 있으니 참고하면 풀 수 있다. 

 

1. 높이와 넓이를 선언한다
2. 주어진 배열을 탐색해야 하므로 2중 반복문을 통해 탐색한다 
3. 메모 제이 션 기법을 활용해 이미 계산된 부분은 계산하지 않도록 주의한다
4. 기준 배열에서 왼쪽 위 , 위 , 대각선 중에 제일 작은 정사각형이 최소 값이 되므로 min 함수를 사용한다.
5. return 값은 정사각형의 크기 이므로 크기는 변 X 변 이기 때문에 **2를 통해 제곱을 해준다.