[백준] 1963번 문제 (소수 경로) 파이썬(Python) 풀이

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

from collections import deque
import sys
input = sys.stdin.readline

def is_prime(num):
    if num < 2:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

def check(num, index, depth):
    global q
    pivot = list(str(num))
    del pivot[index]
    for i in range(10):
        pivot.insert(index, str(i))
        changed_num = int("".join(pivot))
        if changed_num >= 1000 and primes[changed_num] and not visited[changed_num]:
            q.append([changed_num, depth])
        del pivot[index]

primes = [is_prime(i) for i in range(10000)]
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    visited = [False] * 10000
    q = deque()
    q.append([n, 0])
    while q:
        num, depth = q.popleft()
        visited[num] = True
        if num == m:
            print(depth)
            break
        else:
            for i in range(4):
                check(num, i, depth + 1)

primes에 0 ~ 9999 중에 is_prime 함수로 소수 여부를 파악해서 소수이면 True 아니면 False를 저장해놨다.

그 후 check 함수를 통해 숫자를 바꿔가면서 bfs를 통해 탐색의 범위를 넓혀가며 (depth를 += 1 해가며..) 문제를 풀었다.

 

check 함수에서 살펴볼만한 내용은 아래와 같다.

if changed_num >= 1000 and primes[changed_num] and not visited[changed_num]:
	q.append([changed_num, depth])

queue에 append 하는 조건은 해당 숫자가 아래와 같아야 한다.

1. 1000 보다 같거나 크고,
2. 소수이면서,
3. 한 번도 방문한 적이 없어야 한다.

코드가 길고, 시간도 꽤 걸리지만 처음부터 끝까지 온전히 나의 생각으로만 풀려서 뿌듯했다.