소수경로 (백준 파이썬 BFS , 문자열)

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

1963번: 소수 경로

 

알고리즘을 너무 안 풀었더니 너무 오랜시간동안 붙잡고 풀었다.

소수판별하는 방법은 은근히 자주 보이는 것 같다. 제대로 숙지할 필요가 있어보인다. 

 

애먹은 부분 

문자열에서 특정 인덱스 변경하는 것은 C가 오히려 쉬운 것 같다.

list( ) / join( ) 을 사용하는 방법과 slicing을 하는 두가지 방법이 있다. 

https://pythonexamples.org/python-string-replace-character-at-specific-position/

Python String – Replace character at Specific Position - Python Examples

 

 

from collections import deque

prime = [True for _ in range(10000)]
for i in range(2,100):
    if prime[i]==True:    
        n = i
        multiple = 2
        while n*multiple < 10000:
            prime[n*multiple] = False
            multiple += 1

N = int(input())

def solution(src, dst):
    visited = [True for _ in range(10000)]
    que = deque()
    cnt=0
    que.append([src, cnt])
    visited[int(src)]=False
    while que:
        number,cnt=que.popleft()
        if number == dst:
            print(cnt)
            return
        cnt+=1
        for i in range(4):
            for j in range(10):
                
                number_new = list(number)
                number_new[i]=str(j)
                number_new="".join(number_new)
                number_new=int(number_new)
                if prime[number_new] and number_new>1000 and visited[number_new]:
                    visited[number_new]=False
                    que.append([str(number_new),cnt])

    print('Impossible')
    return


for i in range(N):
    src, dst = map(str, input().split())
    solution(src, dst)