[백준] 1915 - 정사각형 🔳 (Python) / 골드 4 / DP
- Programming/알고리즘
- 2022. 11. 10.
1. 문제🔥
링크: https://www.acmicpc.net/problem/1915
문제를 요약하자면, 배열 내에서, 1로 된 가장 큰 정사각형의 크기를 출력해야 합니다.
1) 예제 입출력❄️
예제에서는 가운데 1로 된 2x2 배열이 가장 큰 정사각형이고, 넓이는 4이므로, 4를 출력합니다.
2. 핵심 논리☢️
dp 테이블을 배열과 같은 크기로 하고, 각 행과 열에 그 (행, 열)을 오른쪽 아래 모서리로 하는 최대 정사각형의 한 변 길이를 저장하도록 하는 게 핵심입니다.
3. 풀이 코드✅
1) 코드
n,m = map(int,input().split())
arr = [list(input()) for _ in range(n)]
dp = [[0]*m for _ in range(n)]
result = 0
def check_size(r,c):
if 0<r<n and 0<c<m:
left = int(dp[r][c-1])
up = int(dp[r-1][c])
left_diag = int(dp[r-1][c-1])
return min(left, up, left_diag) + 1
return 1
for r in range(n):
for c in range(m):
if arr[r][c]=='1':
dp[r][c] = check_size(r,c)
result = max(result, dp[r][c])
print(result**2)
주어진 배열의 행(n) 열(m)의 개수를 입력받습니다. 그리고 배열을 입력받아 arr에 저장하고, dp 테이블을 배열과 같은 크기로 하여 값을 0으로 초기화해줍니다. dp테이블의 의미는 각 행, 열에서 그 부분을 정사각형의 오른쪽 아래 모서리로 하는 한 변의 최대 길이를 의미합니다. 최종 출력 값을 result에 0으로 초기화해줍니다. check_size함수는 행(r)과 열(c)을 입력받아, 그 행과 열을 오른쪽 아래 모서리로 하는 정사각형의 최대 한 변 길이를 반환하는 함수입니다.
이제 행을 r로, 열을 c로 이중 for문을 통해 반복하며, 배열에서 그 크기가 '1'인 경우, 해당 부분을 오른쪽 아래로 하는 정사각형 한 변 길이를 check_size함수를 통해 반환받아 dp[r][c]에 넣고, result에 최댓값을 갱신해 나갑니다.
최종 result에는 정사각형 최대 한변 길이가 저장되고, 출력은 정사각형의 넓이 이므로, 제곱해서 출력합니다.
2) 주석달린 코드
n,m = map(int,input().split()) # 행, 열의 개수 입력
arr = [list(input()) for _ in range(n)] # 배열 입력
dp = [[0]*m for _ in range(n)] # dp 0으로 초기화
result=0 # 최종 출력값 0으로 초기화
def check_size(r,c): # r행, c열에 대해 정사각형 한 변 크기 반환
if 0<r<n and 0<c<m:
left = int(dp[r][c-1])
up = int(dp[r-1][c])
left_diag = int(dp[r-1][c-1])
return min(left, up, left_diag) + 1 # r행, c열 기준 위, 왼쪽, 왼쪽위 중 최소값 + 1을 반환
return 1 # 모서리쪽인 경우 정사각형 크기는 아무리커도 1이므로 1 반환
for r in range(n):
for c in range(m):
if arr[r][c]=='1': # 1일 때
dp[r][c] = check_size(r,c) # 한변 크기 반환
result = max(result, dp[r][c]) # 최대 한변 크기를 result에 갱신
print(result**2) # 제곱해서 출력 → 정사각형 넓이 출력
읽어주셔서 감사합니다.
다음에 더욱 유익한 글로 찾아오겠습니다.
* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.
Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/
'Programming > 알고리즘' 카테고리의 다른 글
[백준] 1007 - 벡터 매칭 🔀 (Python) / 골드 2 / 브루트포스 (0) | 2022.11.29 |
---|---|
[백준] 16439 - 치킨치킨치킨 🍗 (Python) / 실버 4 / 브루트포스 (0) | 2022.11.28 |
[백준] 1106 - 호텔 🏨 (Python) / 골드 5 / DP (0) | 2022.11.09 |
[백준] 9625 - BABBA 🆎 (Python) / 실버 5 / DP (0) | 2022.11.08 |
[백준] 1309 - 동물원 🦁 (Python) / 실버 1 / DP (0) | 2022.11.07 |