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

문제

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

1051번: 숫자 정사각형

 

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
square= []

for i in range(N):
    square.append(list(input().strip()))

min_line = min(N, M)
size = 1
for i in range(N):
    for j in range(M):
        # 정사각형을 만들기 위해 N, M 둘 중 짧을 것을 체크
        for k in range(1, min_line):
            # 정사각형 조건이 되면서, 각 꼭지점의 크기가 같을 때
            if i + k < N and j + k < M :
              if square[i][j] == square[i+k][j] == square[i][j+k] == square[i+k][j+k]:
                  size = max(size, (k+1)**2)
print(size)

해설

자세한 것은 주석 참조

 

1. 최대 정사각형 크기를 찾는다

2. 가로 / 세로로 돌아준다

3. 최대 정사각형 크기만큼 돌면서 그 크기를 넘지 않으면서 각 꼭지점의 수가 같을 경우를 찾아 size를 큰 수로 갱신 해준다.