[백준] 1051번 숫자 정사각형 - 파이썬

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

1051번: 숫자 정사각형

문제

숫자로 채워진 직사각형안에서 각 꼭지점이 같은 숫자로 이루어진 정사각형은 찾는문제

입력

첫번째 줄 => N: 세로 길이 M: 가로길이

두 정수가 공백을 사이에 두고 한줄에 나오기에 map(int, input().split())로 받아준다.

 

두번째 줄 => N번 길이가 M인 숫자들이 나온다.

rect = [list(map(int,input()) for _ in range(N)) 2차원리스트로 받아준다. 

만일 내장함수인 map( )이 익숙하지 않다면 한번 익히고 오는것이 좋다

풀이

완전탐색을 이용해서 주어진 사각형의 한줄마다 같은 수가 있는지 확인할 것이다. 만일 같은 숫자를 발견하면 둘의 간격을 계산해서 chcek함수로 아래에도 똑같은 숫자가 있는지 확인해본다.

# 1051번 숫자 정사각형
N, M = map(int, input().split())
rect = [list(map(int, input())) for _ in range(N)]
maximum = [1]

# 똑같은 간격으로 아래줄에도 똑같은 숫자가 존재하는지 확인해본다
# 1, rect[i+간격]에도 같은 숫자가 있는지 확인 2, rect[i+간격]와 rect[i]가 같은지 확인
def check(j ,k, com):
    if rect[i+k-j][j] == rect[i+k-j][k] and com == rect[i+k-j][j]:
        return (k-j+1)**2
    else:
        return 0

# 완전탐색 실시
for i in range(N):
    for j in range(M-1):
        for k in range(j+1, M):
            if rect[i][j] == rect[i][k]:
            # 범위를 벗어나지않는다면..
                if (k - j) <= (N-i-1):
                    maximum.append(check(j, k, rect[i][j]))
                    
print(max(maximum))

출력결과