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

문제

https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

---

풀이 방법

n과 m이 50보다 작거나 같은 자연수이므로 완전 탐색으로 가능하다 생각하여 삼중 for문을 이용하여 풀이했습니다.

n x m에서 나올 수 있는 가장 큰 정사각형부터 감소하는 방향으로  for문을 작성하고,

왼쪽 위의 꼭짓점이 될 수 있는 i, j를 이중 for문으로 모두 탐색합니다.

0,0 ([i][j])부터 변의 길이가 s인 정사각형의 꼭짓점을 비교하여 모두 같다면 정사각형의 크기를 출력하고 종료합니다.

(큰 정사각형부터 작아지는 방향이기 때문에 처음으로 조건문을 만족한 것이 정답이 됩니다.)

---

코드

n, m = map(int, input().split())
li = list(input() for _ in range(n))

for s in range(min(n, m) - 1, -1, -1):
    for i in range(n - s):
        for j in range(m - s):
            if li[i][j] == li[i][j+s] == li[i+s][j] == li[i+s][j+s]:
                print((s + 1)**2)
                exit()