[ BOJ ] 1025 : 제곱수 찾기 ( GOLD 5 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/1025)

문제

N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.

연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.

입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.

출력

첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.

풀이 과정

백트래킹처럼 보이는 브루트포스로 풀이했다.

N x M 표에서 시작점 하나를 잡고, 방향, 행이 증감할 값, 열이 증감할 값을 정해서 정수를 만든다.

만든 정수가 제곱수라면 result = max(result, now) 를 통해 만들 수 있는 가장 큰 완전 제곱수를 찾았다.

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
arr = [list(map(int, list(input().rstrip()))) for _ in range(n)]

row = [-1, 1, 0, 0, -1, -1, 1, 1]
col = [0, 0, -1, 1, -1, 1, -1, 1]

result = -1
def backtracking(now, y, x, rowd, cold, dir):
    global result
    global row
    global col

    if int(''.join(map(str, now))) == int(int(''.join(map(str, now)))**0.5)**2:
        result = max(result, int(''.join(map(str, now))))

    if dir == -1: # 방향 정하기
        for d in range(8):
            for i in range(1, 9):
                for j in range(1, 9):
                    backtracking(now, y, x, i, j, d)
    else:
        if 0 <= y + row[dir]*rowd < n and 0 <= x + col[dir]*cold < m:
            now.append(arr[y + row[dir]*rowd][x + col[dir]*cold])
            backtracking(now, y + row[dir]*rowd, x + col[dir]*cold, rowd, cold, dir)
            now.pop()


for i in range(n):
    for j in range(m):
        backtracking([arr[i][j]], i, j, 0, 0, -1)

print(result)