[baekjoon] 1025 제곱수 찾기[python]

문제가 제일 이해하기 어려웠다.
내가 난독증이 있나 의심했던 것 같다.

첫 쨋 줄에 표의 가로, 세로 사이즈가 들어오고
그 아래로 행과 열의 숫자들을 입력해준 다음,
일정 (행,열)등차의 인덱스 문자들이 문자열로 붙었을 때, 가장 큰 제곱수를 찾는 문제이다.

힌트에 브루트포스(무식한 힘)알고리즘이라고 되어있어 그냥 전부 다 탐색하는 개무식한 알고리즘을 사용했다.

접근

전체 숫자를 다 다른 등차로 찾아서 max값을 출력해야될 것 같다는 생각이 들었다.

• 모든 행과 열 i,j 순회
• -등차도 가능하므로 행 등차(-n ~ n), 열 등차(-m ~ m)까지 설정하여 시작 [i][j]에서 시작해 모든 등차 순회 후 제곱수 여부를 확인하고 더 큰 제곱수라면 해당 값으로 초기화해준다.

코드는 다음과 같다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
board = [list(input().strip()) for _ in range(N)]   #표
answer = -1 #제곱수가 담길 변수

def sqrt_check(S):
    S = int(S)
    return int(S ** 0.5) ** 2 == S


for i in range(N): #시작 x좌표
    for j in range(M): # 시작 y좌표
        for row_d in range(-N,N): # 행의 각 등차 0도 가능
            for col_d in range(-M,M): # 열의 각 등차 0도 가능
                S = ""
                x,y = i,j
                if row_d == 0 and col_d == 0:   #하지만 행과 열 둘 다 등차가 0이 되면 무한루프에 빠지므로 예외처리 해준다
                    continue
                while 0 <= x < N and 0 <= y < M:    #인덱스 범위안에 드는지 확인
                    S += board[x][y]
                    if sqrt_check(S):
                        answer = max(answer,int(S)) #기존 최대 제곱수와 새 제곱수 중 더 큰 값으로 초기화
                    x += row_d  #등차 더해줌
                    y += col_d  #등차 더해줌
print(answer)