[BOJ/백준] 1963 소수 경로

import sys
 
input = sys.stdin.readline
def findprimenumber():
    global prime_number
    prime_number[1] = False
    prime_number[0] = False
    for i in range(2,10001):
        if prime_number[i]:
            for j in range(i+i,10001,i):
                prime_number[j] = False
 
 
 
 
 
T = int(input())
prime_number = [True]*10001
findprimenumber()
for _ in range(T):
    A,B = map(int,input().split())
    result = 'Impossible'
    visited = [-1] * 10001
    if A == B:
        print(0)
    else:
        stack = [A]
        cnt = 0
        while stack:
            new_stack = []
            for number in stack:
                number_list = list(map(int,list(str(number))))
                for ind in range(4):
                    if ind == 0:
                        for k in range(1,10):
                            if number_list[ind] != k:
                                new_number = k*1000 + 100*number_list[1] + 10*number_list[2] + number_list[3]
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
                    else:
                        for k in range(10):
                            if number_list[ind] != k:
                                new_number = number - number_list[ind]*(10**(3-ind)) + k*(10**(3-ind))
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = new_stack[:]
            cnt += 1
        print(result)
        
        

문제는 소수를 구하는 것과 BFS를 활용하면 되는 문제였다.

먼저 자신만의 방법으로 문제에서 주어진 10000 까지의 소수를 구한다.

나는 단순하게 반복문을 통해서 구했고, True False로 구분이 되게 해주었다.

 

이 상황에서 주어진 넘버에서 각자리 수를 변경하면서, 방문하지 않았고 소수일때에 new_stack에 넣어주는 방식으로 했다.

 

 

import sys
 
input = sys.stdin.readline
 
 
prime_number = [True]*10000
prime_number[0] = False
prime_number[1] = False
 
for k in range(2,10000):
    if prime_number[k]:
        for j in range(k+k,10000,k):
            prime_number[j] = False
 
T = int(input())
 
for _ in range(T):
    A,B = map(int,input().split())
    if A == B:
        print(0)
    else:
        visited = [True]*10000
        result = 'Impossible'
        stack = [A]
        cnt = 0
        while stack:
            new_stack = set()
            for number in stack:
                for k in [1,10,100,1000]:
                    fall_number = number - (number//k)%10*k
                    for i in range(10):
                        new_number = fall_number + i *k
                        if prime_number[new_number] and visited[new_number] and new_number >= 1000:
                            visited[new_number] = False
                            new_stack.add(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = list(new_stack)[:]
            cnt += 1
        print(result)

 좀 더 깔끔한 방법으로 자리수 변경을 한 방식이다. 주어진 넘버에서 바꾸고 싶은 자리수로 나눈 몫의 10으로 나눈 나머지를 구하면, 해당 자리수를 구할 수 있다. 이 방식을 이용해서, 구현했다.