백준 1051 : 숫자 정사각형 ( Python )

본문 링크

📌 사용 알고리즘 : implementation

모든 정점에 대해 정사각형이 같은지 확인해줍니다.

시간복잡도는 $O(NM×min(N,M))$ 입니다.

(i,j) 번째 정점에 대해 K×K 크기의 정사각형을 판단하기 위해서는
(i+K-1,j) , (i,j+K-1) , (i+K-1 , j+K-1) 정점을 확인해주면됩니다.

📌 코드

import sys
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

N,M=MI()

graph=[ list(input().rstrip()) for _ in range(N) ]

for i in range(N):
    for j in range(M):
        graph[i][j] = int(graph[i][j])

answer = 1
for i in range(N):
    for j in range(M):
        value = graph[i][j]
        count = 1
        while i+count<N and j+count<M:
            if [ graph[i+count][j] , graph[i][j+count] , graph[i+count][j+count] ] == [value,value,value]:
                answer = max(answer, count+1)
            count+=1

print(answer*answer)