파이썬 알고리즘 : 소수 경로
2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 골드 4 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import sys from heapq import heappop, heappush def check(k:int): if not k%2: return False for i in range(3,int(k**(0.5))+1): if not k%i: return False else: return True prime_numbs = [ False for _ in range(10000)] for i in range(1000,10000): if check(i): prime_numbs[i] = True def change_num(arr: list): result = [] for i in range(10): for j in range(4): tmp = arr.copy() tmp[j] = str(i) if int("".join(tmp)) > 999 and prime_numbs[int("".join(tmp))] and tmp != arr: result.append(tmp) return result t = int(sys.stdin.readline()) for _ in range(t): answer = 'Impossible' a,b = map(int,sys.stdin.readline().split()) visited = [False for _ in range(10000)] visited[a] = True q = [] a_arr = list(str(a)) b_arr = list(str(b)) heappush(q,[0,a_arr]) while q: cnt, now = heappop(q) if now == b_arr: answer = cnt break change_arr = change_num(now) for num in change_arr: if not visited[int("".join(num))]: visited[int("".join(num))] = True heappush(q,[cnt+1, num]) print(answer) 매 번 소수 여부를 체크하지 않고, 1000부터 9999까지 소수 여부를 표시한 배열을 만들었다. change_num() 함수는 특정 수에서 1자리만 바꾼 수이다. 배열에 넣을 때, 몇 번 바뀌었는지를 함께 넣고 최소힙을 이용하여 최대한 적게 바꿀때를 찾을 수 있도록 했다. ...