[백준] 1051번 숫자 정사각형

출처: [백준] 1051번 숫자 정사각형

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10235	3747	3173	37.528%

---

문제

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

---

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

---

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

---

예제 입력 1

3 5
42101
22100
22101

예제 출력 1

9

---

출처

• 빠진 조건을 찾은 사람: adh0463
• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: jh05013

---

알고리즘 분류

• 구현
• 브루트포스 알고리즘

---

소스코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
rectangle = [list(map(int, input().rstrip())) for _ in range(N)]

max_edge = min(N, M)
result = 0
for i in range(N):
    for j in range(M):
        for k in range(max_edge):
            if i + k < N and j + k < M:
                if rectangle[i][j] == rectangle[i][j + k] == rectangle[i + k][j] == rectangle[i + k][j + k]:
                    result = max(result, (k + 1) ** 2)
print(result)