BOJ 1051번 숫자 정사각형 파이썬

문제

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

입력

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

출력

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

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

max_dist = 0
max_result = 0

for i in range(N):
    for j in range(M):
        V = rect[i][j]
        max_dist = 0
        for k in range(min(N, M)):
            # 정사각형 범위를 벗어나면 break
            dist = abs(j - k)
            # 가장 멀리 떨어져있는 점을 구하기 위해서 max_dist 갱신
            if V == rect[i][k]:
                max_dist = max(max_dist, dist)
                # 가장 큰 정사각형의 넓이를 구하기 위해서 max_result 갱신
                if i+max_dist<N and V == rect[i+max_dist][j] and V == rect[i+max_dist][k]:
                    size = (max_dist+1)**2
                    max_result = max(max_result,size)

print(max_result)

N,M이 주어지는 범위가 작기 때문에 (N,M≤50) 브루트포스로 풀 수 있다.

문제에서는 최대 크기의 정사각형을 요구하기 때문에 max로 갱신하면서 가장 큰 경우의 수를 골라야 한다.

가로변에서 반복문을 돌다가 같은 숫자를 찾았다면, 양 수간의 거리를 인덱스 삼아서 바로 나머지 꼭지점에 접근할 수 있다.

만약 그 거리의 꼭지점에 있는 숫자도 값이 같다면, 넓이를 구해서 최댓값과 비교해서 갱신해준다.

주의할 점은 숫자 하나도 하나의 정사각형으로 취급하기 때문에 거리를 구하고 +1를 해주어야 한다.