백준 1051번 - 숫자 정사각형 / Python

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

1051번: 숫자 정사각형

문제 설명

문제

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

입력

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

출력

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

---

정답

N, M = map(int, input().split())

d = min(N, M)

array = []
for _ in range(N):
    array.append(list(map(int, input())))

answer = 1
for i in range(N):
    for j in range(M):
        for k in range(1, d):
            if i + k < N and j + k < M:
                n = array[i][j]
                if n == array[i + k][j] and n == array[i][j + k] and n == array[i + k][j + k]:
                    answer = max(answer, (k + 1) ** 2)

print(answer)

 

---

풀이

N, M = map(int, input().split())

d = min(N, M)

array = []
for _ in range(N):
    array.append(list(map(int, input())))

answer = 1
for i in range(N):
    for j in range(M):
        for k in range(1, d):
            if i + k < N and j + k < M:
                n = array[i][j]
                if n == array[i + k][j] and n == array[i][j + k] and n == array[i + k][j + k]:
                    answer = max(answer, (k + 1) ** 2)

print(answer)

 주어진 숫자들에서 각 꼭짓점의 합이 최대가 되는 정사각형을 찾는 문제입니다. 숫자의 범위가 50*50*50으로 크지 않아  브루트 포스 방식으로 문제를 해결할 수 있습니다.