[백준/파이썬]1963 소수 경로

문제

백준1963번 소수 경로

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

1963번: 소수 경로

 

에라토스테네스의 체로 소수 구하고 너비 우선 탐색으로 조건 만족할 때까지 모든 경우를 탐색했다.

 

BFS는 참 유용한 것 같다.

 

문제는

 

소수인 시작 번호 4자리와 목표 번호 4자리가 주어진다.

 

시작 번호부터 한 자리씩 숫자를 바꿔가며 목표 번호를 만들어 가는 문제다.

 

단, 시작 번호에서 목표 번호까지 1자리씩 숫자를 바꿔 갈 때도 모두 소수로 바꿔가야 한다.

 

풀이

우선 10000크기의 리스트를 만들어 준 뒤, 에라토스테네스의 체를 이용해 각 index값이 소수인지 아닌지 저장해 줬다.

 

이 방식으로 소수를 구하면 빠른 속도로 소수 여부를 알 수 있다.

 

예시)

100이 소수인지 알고 싶을 때,

prime_number[100]를 출력하면 소수가 아니므로 0이 출력된다.

 

 

다음으로 시작 번호부터 한 자리씩 변경해 본다.

 

나는 한 자리씩 바꾸기 위해 int를 문자열로 바꾸고, 그 후 다시 리스트로 바꾼 후 각 자릿수를 바꾸면서 소수인지 확인했다.

now = list(str(queue.popleft()))
for k in range(4) :
    for j in range(0, 10) :
        if k == 0 and j == 0:
            continue
        next = copy.deepcopy(now)
        next[k] = str(j)
        next = int(''.join(next))

 

queue에 1033이 들어있었다면

 

now는 ['1', '0', '3', '3']이 된다.

 

그 후 for문을 이용해 모든 자리에 0~9까지의 수를 바꿔 본다.

 

그 후 만들어진 숫자(next)가 소수인지 판단하고

 

소수라면 queue에 추가해 주는 작업을 하며 bfs탐색을 하면 된다.

 

정답

from collections import deque
import sys
import copy
def bfs() :
    count = 0
    if start_num == end_num :
        print(count)
        return
    while queue:
        count += 1
        queue_len = len(queue)
        for _ in range(queue_len) :
            now = list(str(queue.popleft()))
            for k in range(4) :
                for j in range(0, 10) :
                    if k == 0 and j == 0:
                        continue
                    next = copy.deepcopy(now)
                    next[k] = str(j)
                    next = int(''.join(next))
                    if next == end_num :
                        print(count)
                        return
                    if prime_number[next] == 1 and visit[next] == 0:
                        visit[next]=1
                        queue.append(next)
                        
    print('Impossible')
        
input = sys.stdin.readline

prime_number = [1 for _ in range(10000)]

for i in range(2, 5001) :
    if prime_number[i] == 1 :
            
        for j in range(2, 2501) :
            if i*j >= 10000 :
                break
            prime_number[i*j] = 0
n = int(input())
arr = []
for i in range(n) :
    start_num, end_num = map(int, input().split())
    visit = [0 for _ in range(10000)]
    visit[start_num] = 1
    queue = deque()
    queue.append(start_num)

    bfs()