Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 1051 숫자 정사각형
백준 1051 숫자 정사각형
문제
NxM 크기의 직사각형이 있으며 각 칸에는 한 자리 숫자가 적혀있다.
이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오.
입력
- 첫 번째 줄: N, M
- 두 번째 줄 ~: N개의 수
출력
정사각형의 크기
해결 방식
- n, m중 작은 값이 정사각형 최대 길이: min(n, m)번 반복
- 간격이 s만큼 떨어진 부분의 숫자가 모두 같은지 확인한다.
- 같을 경우 result를 정사각형의 넓이로 갱신
- 최대 정사각형의 크기 출력
코드
n, m = map(int, input().split())
numbers = [list(map(int, list(input()))) for _ in range(n)]
result = 1
size = min(n, m)
for s in range(0, size):
for i in range(n-s):
for j in range(m-s):
if numbers[i][j] == numbers[i][j+s] == numbers[i+s][j] == numbers[i+s][j+s]:
result = (s + 1) ** 2
print(result)
