백준/ Gold 4 문제 , 백준 파이썬 1963, 소수 경로 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 1963, 소수 경로 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
어이없는 실수해서 거기서 시간 많이 잡아먹음

 

 

문제 출처

 

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

1963번: 소수 경로

 

풀이

 

 

1. 소수 저장

 

에라토스테네스의 체 를 이용하여 소수 구간 만들어 두기

 

 

 

2. BFS

 

코드를 잘 작성하였다 생각했는데 이상하게 답이 안나왔다.

 

알고보니 나는 

 

for문 내에서 문자를 변경할때

 

tmp[i]=str(j)

이런식으로 변경해줬었는데, 이러면 원래 문자가 훼손되게 된다.

 

그래서 다음 for문을 계속 돌때 탐색할 수 있는 숫자들이 줄게 되어 답이 안나오던 것이였다.

 

NUM=int(tmp[:i] + str(j) + tmp[i+1:])

 

이런 식으로 작성해줘야지 tmp 변수의 훼손도 안생기고 모든 경우의 수들을 다 확인할 수 있다.

 

 

 

 

3. 입력 받기 및 BFS 호출

 

BFS 내에서 답이 나오지 않는다면 None 이 리턴되니 그에 맞는 출력을 해주자.

 

 

 

 

정답

 

 

 

 

from collections import deque

prime=[True]*10001
prime[0],prime[1]=False,False

for i in range(2,101):
    if prime[i]==True:
        for j in range(i+i,10001,i):
            prime[j]=False
    
def bfs(x,y):
    dq=deque()
    dq.append([x,0])
    visitied=[False]*10001
    visitied[x]=True
    while dq:
        num,cnt=dq.popleft()
        tmp=str(num)
        for i in range(4):
            for j in range(10):
                if i==0 and j==0:
                    j+=1
                NUM=int(tmp[:i] + str(j) + tmp[i+1:])
                if prime[NUM]==True and visitied[NUM]==False:
                    dq.append([NUM,cnt+1])
                    visitied[int(NUM)]=True
                    if NUM==y:
                        return cnt+1
                    
for i in range(int(input())):
    start,end=map(int,input().split())
    if start==end:
        print(0)
    else:
        result=bfs(start,end)
        if result==None:
            print('Impossible')
        else:
            print(result)