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

---

1. 전체 코드

def solution(board):
    depth = len(board)
    width = len(board[0])
    dp = [[0] * width for _ in range(depth)]
    # 첫 행의 1값 dp 저장
    for i in range(width):
        if board[0][i] == 1:
            dp[0][i] = 1
    # 첫 열의 1값 dp 저장
    for i in range(depth):
        if board[i][0] == 1:
            dp[i][0] = 1
    for i in range(1, depth):
        for j in range(1, width):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    answer = dp[0][0]
    for i in range(depth):
        for j in range(width):
            answer = max(answer, dp[i][j])
    return answer * answer

---

2. 후기

비슷한 느낌의 구현 문제를 풀어봤던 경험이 있어서 구현 할 생각으로 한참을 생각했지만 생각보다 너무 어려웠다. 결국 검색을 해봤는데 이 문제는 다이나믹 프로그래밍을 통해 풀어야 한다. 구현으로 안될 것 같으면 다이나믹 프로그래밍을 떠올려야겠다.

직접 생각해서 푼 문제가 아니기 때문에 풀이 링크를 첨부합니다.
[알고리즘 문제 해설] 문제 해설