[구현/브루트포스] 백준 1051 숫자 정사각형 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1051번: 숫자 정사각형

 

 

2. 문제 풀이

 N, M 크기의 숫자 직사각형이 주어집니다. 1~9까지의 숫자가 나열된 직사각형에서 네 모퉁이가 모두 같은 가장 큰 정사각형의 넓이를 구해야 합니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 별다른 방법이 없습니다. (0, 0)부터 (N-1, M-1)까지 순회하며 네 모퉁이가 같은 정사각형이 있는지 탐색합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())  # 가로, 세로
square = []
for _ in range(N):
    square.append(list(input()))

# 가장 큰 정사각형 찾기
size = min(N, M)
for k in range(size, 0, -1):
    for i in range(N):
        for j in range(M):
            # 직사각형 범위 안이면서, 정사각형이면 출력
            if ((i + k) < N) and ((j + k) < M) and (square[i][j] == square[i][j + k] == square[i + k][j] == square[i + k][j + k]):
                print((k+1)**2)
                exit()
# 정사각형이 없으면 1 출력
else:
    print(1)

 

 정사각형의 최대 크기는 (N, M) 중 작은 변의 길이로 결정됩니다. 작은 변의 길이부터 시작해서 1씩 줄여가며, (0,0)부터 (N-1, M-1)까지 네 모퉁이가 같은 정사각형이 있는지 탐색합니다.

 정사각형을 찾으면 바로 출력하고 탐색을 종료합니다. 만약 없다면, 최소 크기인 1를 출력합니다.