[백준] 1051 : 숫자 정사각형 - Python

숫자 정사각형

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

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")

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

g = [list(map(int, input())) for _ in range(n)]

res = 1
length = min(n,m)

def check(x,y,h):
    if 0<=x+h<n and 0<=y+h<m:
        if g[x][y] == g[x][y+h] and g[x][y] == g[x+h][y] and g[x][y] == g[x+h][y+h]:
            return True
        else:
            return False
    else:
        return False

for h in range(1,length + 1): #높이는 2~length 모두 둘러봄
    for x in range(n):
        for y in range(m):
            if check(x,y,h) == True:
                res = (h+1) ** 2

print(res)

👻 코멘트

먼저 모든 좌표를 돌아야 한다는 생각을 했어야 했다. 전체 큰 틀로 돌지만 높이에 따라서 돌았어야 했음.

• 가능한 높이를 점점 높이면서 좌표 하나씩 확인했다면 쉽게 해결 가능.