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

문제

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

1051번: 숫자 정사각형

 

풀이

input이 아래와 같다면, [0][2], [0][4], [2][2], [2][4]를 꼭짓점으로 하는 정사각형이 넓이가 최대가 되는 정사각형이다.

3 5
42101
22100
22101

 

우리는 넓이가 최대가 되는 정사각형을 찾는게 목적이므로, for문을 돌 때 최대 크기부터 하나씩 줄여가며 시작한다. 

네 꼭짓점이 같으면 True를 리턴하고, 그 때의 변 길이를 제곱하여 넓이를 구한다.

 

 

코드

n, m = map(int, input().split())
square = [list(map(int, input())) for _ in range(n)]

size = min(n, m)  # 최대가 될 수 있는 한 변의 길이

def find_square(s):
    for i in range(n-s+1):
        for j in range(m-s+1):
        
        	# 네 꼭짓점을 이루는 숫자가 모두 같으면
            if square[i][j] == square[i][j+s-1] == square[i+s-1][j] == square[i+s-1][j+s-1]:
                return True
            
    return False
    

# 한 변의 크기가 최대가 되는 숫자부터 하나씩 작아짐
for k in range(size, 0, -1):
    if find_square(k):
        print(k ** 2)
        break