[BOJ] 1025 - 제곱수 찾기 (Python, JavaScript)

 

 

아이디어

 

표에서 조건에 맞게 칸을 이동하며 만들 수 있는 숫자들 중 가장 큰 완전 제곱수를 구한다.

 

 

풀이 #1 (Python)

 

표를 입력 받아 2차원 리스트 table에 저장하고, 만들 수 있는 숫자들을 저장하는 세트 numbers를 생성한다.

차례로 표의 i행 j열에 있는 숫자를 numbers에 추가하고, 행과 열의 공차 di, dj로 함수 make_number를 호출한다.

이때 행과 열의 공차가 모두 0이면 무한 루프에 빠지므로 둘 중 하나라도 0이 아닐 때 함수를 호출하도록 한다.

 

함수 make_numbers는 인덱스를 벗어나지 않는 범위에서 재귀 호출로 공차에 따라 칸을 이동하며 숫자를 이어 붙인다.

이어 붙인 숫자들을 numbers에 추가하며, 공차가 음수인 숫자들을 저장하기 위해 역순으로 이어 붙인 숫자도 추가한다.

 

함수 make_numbers 종료 후 numbers를 내림차순으로 정렬된 리스트로 대체한다.

is_integer 메서드로 number에서 완전 제곱수를 찾으면 그 수를 출력하고, 그렇지 않으면 -1을 출력한다.

 

import sys

input = sys.stdin.readline

def make_number(num, r, c, dr, dc):
    global numbers
    if r+dr < N and 0 <= c+dc < M:
        new_num = num+table[r+dr][c+dc]
        make_number(new_num, r+dr, c+dc, dr, dc)
        numbers.add(int(new_num))
        numbers.add(int(new_num[::-1]))

N, M = map(int, input().split())
table = [[*input().rstrip()] for _ in range(N)]
numbers = set()
for i in range(N):
    for j in range(M):
        numbers.add(int(table[i][j]))
        for di in range(N):
            for dj in range(M):
                if di or dj:
                    make_number(table[i][j], i, j, di, dj)
                    make_number(table[i][j], i, j, di, -dj)
numbers = sorted(numbers, reverse=True)
for num in numbers:
    if (num**0.5).is_integer():
        print(num)
        break
else:
    print(-1)

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 같은 방식으로 동작한다.

자바스크립트에서는 문자열을 뒤집으려면 시간이 더 오래 걸리므로 함수 호출 시 음수인 공차를 인자로 넘겨 처리한다.

제곱근이 1로 나누어 떨어지면 res에 그 수를 저장하여 출력하고, 그렇지 않으면 res의 초기값 -1을 출력한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function makeNumber(num, r, c, dr, dc) {
    global.numbers;
    if (N > r+dr && r+dr >= 0 && M > c+dc && c+dc >= 0) {
        let newNum = num+table[r+dr][c+dc];
        makeNumber(newNum, r+dr, c+dc, dr, dc);
        numbers.add(Number(newNum));
    }
}
let [N, M] = input[0].split(' ').map(Number);
let table = [];
for (let i=1; i<N+1; i++) {
    table.push(input[i]);
}
let numbers = new Set();
for (let i=0; i<N; i++) {
    for (let j=0; j<M; j++) {
        numbers.add(Number(table[i][j]));
        for (let di=0; di<N; di++) {
            for (let dj=0; dj<M; dj++) {
                if (di || dj) {
                    makeNumber(table[i][j], i, j, di, dj);
                    makeNumber(table[i][j], i, j, di, -dj);
                    makeNumber(table[i][j], i, j, -di, dj);
                    makeNumber(table[i][j], i, j, -di, -dj);
                }
            }
        }
    }
}
numbers = Array.from(numbers);
numbers.sort((a, b) => b-a)
let res = -1;
for (let num of numbers) {
    if (!(Math.sqrt(num)%1)) {
        res = num;
        break
    }
}
console.log(res);