[프로그래머스] 가장 큰 정사각형 찾기 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

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

 

출처: 프로그래머스

---

처음에는 이런 방식으로 접근했다.

지금 현재 방문하고 있는 칸이 1이라면, 대각선 아래방향(↘) 을 먼저 확인해 이게 1이라면 대각선 아래의 상,좌를 확인해 사각형이 구성되는지 확인했다.

 

예제 케이스는 board의 크기가 작기도 하고, 피드백이 바로 가능했기에 맞았지만 테스트케이스는 절반만 맞고 효율성은 통과하지 못했다.

 

BFS를 통해서 row, column 길이에 제한을 두고 풀어볼까 했지만 이 또한 이전 풀이와 시간복잡도가 다르지 않을 것으로 판단했다.

 

DP문제라는 힌트를 듣고서 스스로 풀이에 도전했지만, 결국 해답을 찾지 못해 다른 사람들의 도움을 빌려 문제를 해결할 수 있었다.

 

<정답 코드>

def solution(board):
    answer = 0
    r = len(board) + 1
    c = len(board[0]) + 1
    DP = [[0]*c for _ in range(r)]
    
    for i in range(1, r):
        for j in range(1, c):
            if board[i-1][j-1]:
                DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1])+1
            
            answer = max(answer, DP[i][j])
    
    return answer**2

접근은 아래와 같다.

1. board보다 width, hegith가 1씩 더 큰 dp 배열을 만든다.
2. (1, 1)부터 순회를 시작해서 현재 위치가 1에 board에서 1에 해당한다면, 현재 위치의 상, 좌, 대각선 좌측 위(↖) 중에서 가장 작은 값 +1 로 업데이트 한다.

풀이가 생각보다 간단한 것에 놀랬고, 언제 쯤 이런 생각을 바로바로 떠올릴 수 있게 될까 내심 걱정도 됐다.