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

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

1051번: 숫자 정사각형

문제

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

입력

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

출력

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

 

코드

N, M = map(int, input().split())
sqr = [''] * N
min_box = min([N, M])
max_box = 1

for i in range(N) :
    sqr[i] = input()

for box_now in range(0, min_box) :
    for i in range(0, N * M) :
        row = i// M
        columm = i - row * M
        if row + box_now <= N-1 and columm + box_now <= M-1 :
            if list(sqr[row])[columm] == list(sqr[row+box_now])[columm] == list(sqr[row])[columm+box_now] == list(sqr[row+box_now])[columm+box_now] :
                max_box = box_now + 1
print(max_box ** 2)

 

풀이

구해야 할 정사각형의 한변의 길이의 최대는 N x M 길이의 직사각형의 가장 작은 변의 길이이다. 이를 min_box라는 변수에 저장했다. sqr에 직사각형의 숫자들을 입력 받은 후, 정사각형 한 변의 길이가 1부터 min_box까지인 경우를 매 칸마다 조사한다. 다만 조사하는 칸이 sqr 범위 밖을 넘어가지 않도록 미리 조건을 설정했다.