백준 1051번: 숫자 정사각형

문제 설명

• 2x2배열을 순회하면서 정사각형을 찾는 문제입니다.

접근법

• 특별한 아이디어가 떠오르지 않아 입력된 수를 전부 순회했습니다.
• 하나의 값에 대해 정사각형이 완성되는 범위 내에서 변의 길이를 1씩 확장시켜 그때마다 꼭짓점의 값이 일치하는지 확인합니다.
  • 정사각형이 되려면 가로변과 세로변이 전부 2x2행렬 내부에 있어야 합니다.

정답

N,M = list(map(int,input().split(" ")))
board = []
for _ in range(N):
    board.append(list(input())) #저는 문자열로 두는 것보다 list에 값을 하나씩 담는 걸 선호합니다.

max_ = 1 

def func(i,j):
    global max_
    c = 1 # 변의 길이입니다
    #현재 위치(i,j)에서 변의 길이를 늘렸을 때 행렬의 범위를 벗어나지 않아야 합니다
    while (i+c<N and j+c<M): 
    	# 네 꼭짓점이 같은 값인지를 판단합니다
        if board[i][j] == board[i+c][j] == board[i][j+c] == board[i+c][j+c]:
            max_ = max(max_,(1+c)*(1+c)) #같다면 이전의 값과 비교해 더 큰 걸 취합니다
        c+=1 #변의 길이는 꼭지점이 같은지 여부와 관계 없이 1씩 증가합니다
        
for i in range(N):
    for j in range(M):
        func(i,j) #모든 입력값에 대해 정사각형 판별을 실행합니다

print(max_)

기타

• 꼭지점이 아니라 내부의 값이 전부 1인 조건의 정사각형 문제도 있었다. https://www.acmicpc.net/problem/4095