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

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

핵심

다른 사람 풀이

def solution(board):
    n = len(board)
    m = len(board[0])

    # dp 준비
    dp = [[0] * m for _ in range(n)]
    dp[0] = board[0]
    for i in range(1, n):
        dp[i][0] = board[i][0]
    
    # 2중 포문으로 연산
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    
    # 최대 넓이 구하기
    answer = 0
    for i in range(n):
        temp = max(dp[i])
        answer = max(answer, temp)
    
    return answer ** 2

다른 사람 풀이 2

def solution(board):
    for row in board: # 정답의 최소값이 0인지 1인지 먼저 판별
        if sum(row): # sum한 결과가 0이면 False, 1이면 True
            answer = 1
            break
    else:
        return 0
	# 1행 1열부터 board를 2x2 정사각형으로 탐색하면서 우측 아래 값 최신화
    for i in range(1, len(board)): # 행
        for j in range(1, len(board[0])): # 열
            if board[i-1][j-1] and board[i-1][j] and board[i][j-1] and board[i][j]:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
                answer = max(answer, board[i][j])
    return answer ** 2