(Python/파이썬) - 백준(BOJ) 1051번 : 숫자 정사각형

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

1051번: 숫자 정사각형

---

• 문제 : 

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

 

 

 

---

• 풀이 :

구현 문제입니다.

 

모든 좌표들에 대해 해당 좌표를 정사각형의 왼쪽 위 꼭짓점이라 가정하고 0부터 n과 m의 min값만큼 변의 길이를 가진 정사각형을 가정하며 해당 사각형의 꼭짓점이 모두 같은 값을 갖고 있는지 확인하면 됩니다. 

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
board = [list(map(int,input().strip())) for _ in range(N)]
max_width = min(N,M)
answer = 0
for i in range(N):
    for j in range(M):
        for k in range(max_width):
            if (i+k) < N and (j+k) < M and (board[i][j] == board[i+k][j] == board[i][j+k] == board[i+k][j+k]):
                answer = max(answer, (k+1)**2)
print(answer)