소수경로 (백준 파이썬 BFS , 문자열)
https://www.acmicpc.net/problem/1963
1963번: 소수 경로
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금
www.acmicpc.net
알고리즘을 너무 안 풀었더니 너무 오랜시간동안 붙잡고 풀었다.
소수판별하는 방법은 은근히 자주 보이는 것 같다. 제대로 숙지할 필요가 있어보인다.
애먹은 부분
문자열에서 특정 인덱스 변경하는 것은 C가 오히려 쉬운 것 같다.
list( ) / join( ) 을 사용하는 방법과 slicing을 하는 두가지 방법이 있다.
https://pythonexamples.org/python-string-replace-character-at-specific-position/
Python String – Replace character at Specific Position - Python Examples
Python – Replace Character at Specific Index in String To replace a character with a given character at a specified index, you can use python string slicing as shown below: string = string[:position] + character + string[position+1:] where character is t
pythonexamples.org
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)