프로그래머스/LV2
[프로그래머스 Lv2,python] - 가장 큰 정사각형 찾기
chyam_eun
2025. 3. 20. 13:41
https://school.programmers.co.kr/learn/courses/30/lessons/12905
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
def solution(board):
m, n = len(board), len(board[0]) # 행, 열
dp = [[0]* n for _ in range(m)]
max_side = 0 # 최대 변 길이
for i in range(m):
for j in range(n):
if board[i][j]==1: # 1일때
if i==0 or j==0: # 첫행, 첫열은 길이 1
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + 1 # 바로 위,왼쪽,대각선부분 중 가장 작은 값 + 1(자신)
max_side = max(max_side, dp[i][j]) # 최대이면 갱신해주기
return max_side**2 # 넓이
처음에 bfs를 사용했는데 안풀려서 찾아봤더니 dp를 사용하는거였다....