[백준] 1915 - 정사각형 🔳 (Python) / 골드 4 / DP

BAEKJOON Logo

 

Contents

 

---

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) # 제곱해서 출력 → 정사각형 넓이 출력

 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1915_%EA%B0%80%EC%9E%A5_%ED%81%B0_%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

 

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/