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

🧑🏻‍💻 문제링크

문제풀이

동적계획법을 사용해서 푸는 문제이다. 처음에 문제를 제대로 안읽어서 엉뚱한 짓만 하다가 문제를 다시 읽어보니깐 숫자가 1인 경우에만 정사각형을 계산하는 것이었다. 앞으로는 시간이 없다고 해서 문제를 제대로 읽고 생각해서 푸는 연습을 해야겠다.

동적계획으로 풀었던 이유는 가장자리의 꼭짓점만 구하면 되기 때문에 동적계획법이라고 생각을 했다. 다른 사람들의 문제 풀이를 보면 list comprehesion을 사용해서 계산을 하던데 나는 아직 익숙하지 않고 코드를 보는 사람들로 하여금 좀 더 가독성 있는 코드를 보여주고 싶기 때문에 그냥 2중 for문을 사용했다.

코드

def solution(board):
    answer = 1234

    n = len(board)      # 세로
    m = len(board[0])   # 가로
    
    temp = []

    for i in range(1, n):
        for j in range(1, m):
            # 표에 1인 것만 계산
            if board[i][j] == 1:
                # 위, 옆, 왼쪽 대각선 위를 계산
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1
    
    for i in board:
        for j in i:
            temp.append(j)

    answer = max(temp) ** 2
    return answer

결과