[Algorithm] (백준) 1051 숫자 정사각형 - 파이썬

(백준) 1051 숫자 정사각형

문제

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

입력

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

출력

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

예제 입력 1

3 5
42101
22100
22101

예제 출력 1

9

풀이

제출

n, m = map(int, input().split())
board=[]
max_n = 0
for i in range(n):
    board.append(list(map(int,input())))

for y in range(n-1):
    for x in range(m-1):
        # x, y 둘 다 왼쪽 위 꼭짓점을 기준으로 찾아주면 되니까 1씩 빼준다.
        key = board[y][x]
        cnt = 1

        while cnt<min(n,m):
            # board 크기 숫자를 넘어가지 않도 cnt와 비교해 준다

            if y+cnt<n and x+cnt<m and board[y][x+cnt]==key and board[y+cnt][x]==key and board[y+cnt][x+cnt]==key:
                # cnt로 정사각형 크기 알 수 있게 해주고 max에 그에 따른 크기 저장
                max_n = max((cnt+1)**2,max_n)
            cnt+=1



print(max_n)