[BOJ] 1963 - 소수 경로 (Python, JavaScript)

 

 

아이디어

 

BFS로 수의 한 자리만 숫자를 바꾼 다른 소수로 변환해 나가며 변환에 필요한 최소 횟수를 구한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

def solution():
    P = [True]*10000
    for i in range(2, 101):
        if P[i]:
            for j in range(i*2, 10000, i):
                P[j] = False
    for i in range(1000):
        P[i] = False
    T = int(input())
    for _ in range(T):
        A, B = map(int, input().split())
        visited = [0]*10000
        visited[A] = 1
        queue = [A]
        while queue:
            num = queue.pop(0)
            if num == B:
                print(visited[num]-1)
                break
            for i in range(4):
                temp = (num//10**(i+1))*10**(i+1)+num%(10**i)
                for n in range(10):
                    temp += n*10**i
                    if P[temp] and visited[temp] == 0:
                        visited[temp] = visited[num]+1
                        queue.append(temp)
                    temp -= n*10**i
        else:
            print('Impossible')

solution()

 

 

 

풀이 #2 (JavaScript)

 

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

function solution() {
    let P = Array(10000).fill(true);
    for (let i=2; i<=100; i++) {
        if (P[i]) {
            for (let j=i*2; j<10000; j+=i) {
                P[j] = false;
            }
        }
    }
    for (let i=0; i<1000; i++) P[i] = false;
    const T = Number(input[0]);
    for (let t=1; t<=T; t++) {
        const [A, B] = input[t].split(' ').map(Number);
        let visited = Array(10000).fill(0);
        visited[A] = 1;
        let queue = [A];
        while (queue.length) {
            const num = queue.shift();
            if (num === B) {
                console.log(visited[num]-1);
                queue.push(0);
                break;
            }
            for (let i=0; i<4; i++) {
                let temp = (parseInt(num/10**(i+1)))*10**(i+1)+num%(10**i);
                for (let n=0; n<10; n++) {
                    temp += n*10**i;
                    if (P[temp] && visited[temp] === 0) {
                        visited[temp] = visited[num]+1;
                        queue.push(temp);
                    }
                    temp -= n*10**i;
                }
            }
        }
        if (queue.length === 0) console.log('Impossible');
    }
}

solution();