BOJ 1963 - 소수 경로

문제

백준 온라인 저지 - 1963번

풀이 과정

목표 지점에 도달하기 위한 최단 경로를 구하는 문제이므로 BFS 를 통해 답을 구했습니다.

우선 현재 숫자에서 변경 가능한 자리수는 총 4개이므로 각 자리수에 0~9의 숫자를 하나씩 넣어보며
그로 인해 생성된 숫자가 소수일 경우 큐에 넣어줬습니다.
이때 소수인지 판별하는 알고리즘은 O(root(N)) 의 시간 복잡도를 가지므로 주어진 제한 시간내에 충분히 수행 가능합니다.

코드

import sys
from collections import deque


def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True

    if n % 2 == 0:
        return False

    sqrtn = int(n**0.5)
    for div in range(3, sqrtn+1, 2):
        if n % div == 0:
            return False

    return True


def bfs(start, goal):
    q = deque()
    visit = [0 for _ in range(10000)]

    q.append((start, 0))
    visit[start] = 1

    while q:
        here, cost = q.popleft()
        if here == goal:
            return cost

        temp = str(here)
        for idx, digit in enumerate(temp):

            for n in range(10):
                if n != int(digit):
                    new = temp[:idx] + str(n) + temp[idx+1:]
                    if is_prime(int(new)) and not visit[int(new)]:
                        q.append((int(new), cost + 1))
                        visit[int(new)] = 1

    return 'Impossible'


if __name__ == '__main__':
    T = int(input())
    for case in range(T):
        frm, to = list(map(int, sys.stdin.readline().split()))
        ret = bfs(frm, to)
        print(ret)