[백준/파이썬/브루트포스] 1051번 숫자 정사각형 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/1051

1051번: 숫자 정사각형

 

문제

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

 

입력

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

 

출력

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

 

정답

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
graph = [sys.stdin.readline().rstrip() for _ in range(n)]

answer = 1

for i in range(n):
    for j in range(m):
        for k in range(answer,50):
            if n<=i+k or m<=j+k:
                break
            if len(set([graph[i][j],graph[i+k][j],graph[i][j+k],graph[i+k][j+k]])) == 1:
                answer = max(answer,k+1)
print(answer**2)

k의 값을 늘려가면서 모든 값이 같을 경우 answr에 값을 넣어주고 제곱을 한 값을 출력해주는 방식입니다.