[BOJ | Python] 1051번: 숫자 정사각형

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

 

문제

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

 

입력

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

 

출력

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

 

풀이

N, M이 50보다 작은 수이므로 완전탐색을 활용하여 풀 수 있다.

def isSquare(n):
    for i in range(N - n):
        for j in range(M - n):
        # 왼쪽 위 꼭짓점인 li[i][j]의 오른쪽, 아래, 대각선 꼭짓점 값 확인
            if li[i][j] == li[i + n][j] == li[i][j + n] == li[i + n][j + n]: 
                return n + 1 # 한 변의 길이 반환
    return 1

N, M = map(int, input().split())
li = [[int(num) for num in input()] for _ in range(N)]
ans = 1 # 답을 저장할 변수, 디폴트 값이 1

for n in range(1, min(N, M)):
    ans = max(ans, isSquare(n))

print(ans**2) # 넓이를 출력해야 하므로 제곱

 

인덱스를 고려할 때 2칸 차이면 한 변이 2인 정사각형...이라고 착각해서 중간에 꼬일뻔 했는데, 다행히 중간에 오류를 발견해서 잘 풀었다!