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

1. 문제

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

프로그래머스

 

2. 접근

1. 처음에 내가 생각한 접근 방법은 모든 행마다 처음으로 나오는 1을 기준으로 정사각형의 넓이를 구하는 것이다.

- 모든 행의 첫번째로 나오는 1을 기준으로 한 이유는 위, 아래, 오른쪽을 판단하면 중간에 끊김 없이 정사각형을 구할 수 있기 때문이다.

- 여기서의 문제는 정사각형의 넓이를 구하는 일이 너무 어렵다...dfs로 하기에도 중간에 0이 나올때 어디서 멈춰야 할지를 모르겠다

 

2. 그래서 구글링 결과 다른 사람들의 접근 방법은 DP였다.

- dp를 주어진 board보다 행 열 모두 1씩 크게 만들어서 왼쪽, 위, 왼쪽위 이렇게 3방향을 보면서 가장 작은 값보다 1씩 증가시킨 값을 dp에 저장하면서 정사각형의 한변의 길이를 구해야 한다

[ 정사각형의 넓이를 구한다는 관념에서 벗어나야 한다 ]

 

 

3. 풀이

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

    return ans ** 2