[백준/파이썬] 1051번 숫자 정사각형 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1051번 숫자 정사각형
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

숫자로 이루어진 N x M 격자에서 네 꼭짓점의 값이 같은 정사각형을 찾고, 그 정사각형의 넓이 최댓값을 구하는 문제입니다.

코드

import sys;read=sys.stdin.readline
n,m=map(int,read().split())
l=[list(map(int,list(input())))for _ in range(n)]
r=1
for t in range(1,min(n,m)):
    for i in range(n-t):
        for j in range(m-t):
            if l[i][j]==l[i+t][j]==l[i][j+t]==l[i+t][j+t]:r=max(r,(t+1)**2)
print(r)

설명

한 변 길이를 t+1로 두고 가능한 모든 시작 좌표 (i, j)를 순회합니다.

각 좌표에서 네 꼭짓점:

• (i, j)
• (i+t, j)
• (i, j+t)
• (i+t, j+t)

값이 모두 같으면 해당 정사각형 넓이 (t+1)^2로 최대값을 갱신합니다.

기본값 1은 1x1 정사각형(항상 가능)을 의미합니다.

---

• 백준 문제풀이 전체 목록 보기

---