[백준][1051] 숫자 정사각형

• Problem Link : https://www.acmicpc.net/problem/1051

문제

• 각 칸에 한자리 숫자가 적인 M*N 칸 크기의 직사각형이 주어진다.
• 이 직사각형에 꼭짓점에 쓰여있는 수가 모두 같은 가장 큰 정사각형을 찾는다.
• 이 때, 정사각형은 행 또는 열에 평행해야한다.

입력

• 첫째 줄, N과 M이 주어진다.
• 다음 줄, N개의 줄에 수가 주어진다.

출력

• 정사각형의 최대 크기를 출력한다.

풀이

M과 N의 길이 중 더 작은 값을 최대 변의 길이로 하는 정사각형까지만 직사각형 안에 존재할 수 있다. 따라서 변의 길이를 2부터 N과 M 중 더 작은 수까지 늘려나가면서 정사각형이 존재하는지를 판단한다.

• 당연하게도 변의 길이가 1인 경우는 칸이 1개라도 존재하면 성립하기 때문에 별도로 확인하지 않는다.
• 행 index와 열 index에 (length-1)을 더해줘서 만들 수 있는 세 점이 기존 행 index, 열 index의 위치한 수와 같은지 비교해서 같다면 정사각형이 존재하므로 최대 넓이를 갱신한 후 다음 length를 진행한다.
  - 필요한 것은 최대 넓이이므로 같은 넓이의 정사각형을 추가로 찾는 것은 시간 낭비이다.
• 중요한 것은 첫 꼭짓점의 행 index와 열 index의 반복 범위를 아래 그림과 같이 n-(length-1), m-(length-1)로 설정해 주어야한다. 그렇지 않으면 index 범위를 벗어나는 오류가 발생한다.

코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(list(input())[:-1])


def find_square(length, ans):
    for i in range(n - (length - 1)):
        for j in range(m - (length - 1)):
            if (
                arr[i][j] == arr[i][j + (length - 1)]
                and arr[i][j] == arr[i + (length - 1)][j]
                and arr[i][j] == arr[i + (length - 1)][j + (length - 1)]
            ):
                return length * length
    return ans


ans = 1
for length in range(2, n + 1):
    ans = find_square(length, ans)

print(ans)