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

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

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

처음에 단순 BFS문제인줄 알고 짱구를 굴려봤는데

도저히 BFS로는 답을 낼 방법이 떠오르지 않았다..

 

보통 이런경우 완전탐색이거나 DP인 경우가 많았던것같은데

완탐은 아닌것같고 DP로 풀면 어떨까 싶어서 코드를 짜봤다.

 

처음에진짜 어려웠던문제 도무지 기억이 안났다

 

푼 방식은 반복문을 돌며 현재값이 1일 경우

그 칸 (좌, 좌위, 위) 의 최소값 +1 로 값을 수정해주면된다

 

 

def solution(board):
    answer = 1
    max_num = 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if i == 0 or j == 0:
                if board[i][j] > max_num:
                    max_num = board[i][j]
            else:
                if board[i][j] == 1:
                    # board[i][j]가 1일경우 좌,좌위,위의 값중 최소값 +1로 숫자를 바꿔준다.
                    board[i][j] = min(board[i][j - 1], board[i - 1][j - 1], board[i - 1][j]) + 1
                    if board[i][j] > max_num:
                        max_num = board[i][j]
 
    answer = max_num * max_num
 
    return answer