[백준] #1051 숫자 정사각형(python)

📌문제

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

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

예제 입력1

3 5
42101
22100
22101

예제 출력1

9

예제 입력2

2 2
12
34

예제 출력2

1

예제 입력3

2 4
1255
3455

예제 출력3

4

예제 입력4

1 10
1234567890

예제 출력4

1

예제 입력5

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

예제 출력5

49

백준 1051번 문제

💡Idea

각 숫자들을 모두 확인해보는 브루트 포스💪로 문제를 해결할 수 있습니다.

각 숫자들을 하나씩 읽어나가면서 만들어지는 정사각형이 있는지, 있다면 현재까지 발견된 최대 정사각형의 크기와 비교하여 더 큰 정사각형을 정답으로 합니다.

👆 위의 그림을 토대로 간단히 설명을 하겠습니다.

배열의 [0, 0] 요소부터 시작하여 차례로 [0, 1], [0, 2]까지 확인하고 있는 그림입니다.
각각 빨간색 -> 노란색 -> 초록색 순서대로 정사각형의 꼭짓점이 모두 같은 숫자인지를 확인하면서 정사각형이 만들어지는지를 확인합니다.

💻코드

• ⏰ 시간 : 84 ms / 메모리 : 30852 KB

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
square = [input() for _ in range(N)]
ans = 1
for i in range(N):
    for j in range(M): # 숫자 하나씩 확인
        for k in range(1, min(N - i, M - j)): #1
            if square[i][j] == square[i][j+k] == square[i+k][j] == square[i+k][j+k]:
            	# 정사각형이 네 꼭짓점이 모두 같은 경우 넓이 계산
                ans = max(ans, (k + 1) * (k + 1))
print(ans)

📝코드 설명

#1 : 현재 위치에서 이동할 수 있는 만큼만 오른쪽, 그리고 아래로 이동합니다.
정사각형이기 때문에, 두 방향으로 이동시 동일한 거리만큼만 이동하며 두 방향 중 이동할 수 있는 거리가 더 적게 남은 만큼만 반복하여 이동합니다.

오른쪽으로 이동할 수 있는 최대 거리 : M - j (가로 길이 - 현재 위치)
아래쪽으로 이동할 수 있는 최대 거리 : N - i (세로 길이 - 현재 위치)