[python] 백준 1051번 - 숫자 정사각형

문제

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

링크 참조

https://www.acmicpc.net/problem/1051

풀이 설명

N X M 크기의 직사각형이 있다고 하면,
그 중에서 가장 크게 생길 수 있는 정사각형의 네 개의 꼭짓점에 위치한 숫자가 같으면
해당 크기를 출력하면 된다.
가장 크게 생길 수 있는 크기를 출력하는 것이 목표이다.

코드

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

for i in range(N):
    A[i] = list(map(int,input()))

ans = []

if N >= M:
    size = M
else:
    size = N

i = 0
j = 0

#A는 A[11][10] 크기임 -> 사실은 A[10][9]까지 밖에 없음.
while size > 0:
    
    if A[i][j] == A[i+size-1][j] == A[i][j+size-1] == A[i+size-1][j+size-1]:
        ans.append(size**2)
    
    j += 1
    
    if j+size-1 >= M:
        j = 0
        i += 1
        
    if i+size-1 >= N:
        size -= 1
        i = 0
        j = 0
        
print(max(ans))

우선 A라는 2차원 리스트에 입력으로 주어진 직사각형 내의 숫자들을 담는다.

이후, N, M 중에서 크기를 결정한다. 위에 그림에서 표현되어 있듯이 두 변 중 더 짧은 것이
가장 maximum인 크기가 된다.

그 다음, 크기가 0이 될 떄까지 반복을 해주면서 사이즈의 네 꼭짓점의 좌표 값이 같은 지 비교해준다.

정사각형의 가로/세로 값이 주어진 직사각형의 크기보다 커지면 행의 값을 늘리고 열의 값은 초기화한다.
(등호 쓴 이유는 배열에서는 크기 -1 까지가 최대값이기 떄문)

행의 값이 주어진 직사각형의 세로 값보다 커지면 해당 사이즈에서는 더이상 경우가 없다는 의미이므로 사이즈를 줄여준다.

해당 조건을 만족하는 사이즈를 ans 배열에 계속 추가를 한 다음, 결과는 최댓값만을 출력한다.

💌

후기

배열에서 index 증감을 잘 확인하자. 같은 로직에서 테스트케이스는 다 맞는데 실패라고 뜨길래
하나하나 index을 출력해봤더니 배열의 끝까지 안가고 있다는 것을 알게 되었다.
꼼꼼하게! 확인하기!