문제
N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.
출력
첫째 줄에 정답 정사각형의 크기를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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를 해주어야 한다.