백준 1051번 숫자 정사각형

 

문제와 입출력 조건은 다음과 같다.

 

 

 

 

N×M 크기의 2차원 배열로 생각을 한다.

배열의 각 칸에는 한 자리 숫자라 했으니 0부터 9까지의 숫자가 적혀 있다.

정사각형의 꼭짓점이 모두 같은 숫자로 이루어져야 한다.

 

 

자 이제 가능한 모든 정사각형의 크기를 생각해야 한다.

크기는 1x1부터 시작하여 최대 N×M의 크기로 나올 수 있다.

1x1 정사각형은 항상 가능하므로 초기 최대 크기를 1로 설정한다.

 

 

정사각형의 크기(size)를 증가시키며 2부터 시작하여 가능한 최대 크기까지 반복하면서 최대 크기를 찾고

현재 정사각형의 크기를 기준으로 가능한 모든 정사각형의 시작 위치를 찾는다.

 

정사각형의 꼭짓점 값들을 비교하고 모든 꼭짓점 값이 동일하다면 현재 정사각형의 크기를 최대 크기(max_size)로 업데이트한다.

 

 

 

정리)

 

- N과 M을 입력받고, N개의 행을 리스트로 저장한다.

- 최대 크기를 1로 초기화한다.

- 정사각형의 크기를 2부터 시작하여 가능한 최대 크기까지 반복한다.

- 각 정사각형의 시작 위치(i, j)에서 꼭짓점의 값을 확인하여 모두 같은지 검사한다.

- 만약 모두 같으면 최대 크기를 업데이트한다.

- 최종적으로 업데이트된 최대 정사각형의 크기를 제곱하여 출력한다.

 

def square(N, M, matrix): # N과 M을 입력받고 N개의 행을 리스트로 저장
    max_size = 1  # 최소 크기는 1x1
    for size in range(2, min(N, M) + 1):  # 정사각형의 크기
        for i in range(N - size + 1):  # 시작 행
            for j in range(M - size + 1):  # 시작 열
                # 정사각형의 꼭짓점 값
                top_left = matrix[i][j]
                top_right = matrix[i][j + size - 1]
                bottom_left = matrix[i + size - 1][j]
                bottom_right = matrix[i + size - 1][j + size - 1]
                
                # 꼭짓점 값이 모두 같은지 확인
                if (top_left == top_right == bottom_left == bottom_right):
                    max_size = size  # 크기 업데이트
    return max_size ** 2  # 크기의 제곱 = 정사각형 면적


N, M = map(int, input().split())
matrix = [input().strip() for _ in range(N)]

# 함수 호출 및 결과 출력
result = square(N, M, matrix)
print(result)