[ 백준 1963 ] 소수 경로 - Python

문제 보기

이 문제는 BFS 문제이다.

입력받은 두 수에서 첫 번째 값을 기준으로 BFS 탐색을 진행하면 된다.

 

알고리즘 순서는 다음과 같다.

1. 첫번째 값을 큐에 넣는다.

2. 큐에 들어있는 값을 가져와서 한 자리씩 값을 수정해보고 소수 조건에 부합한다면 큐에 추가한다.

3. 2번의 과정을 두 번째 수를 찾을 때까지 진행한다.

 

알고리즘은 위와 같이 구성하였고 값을 한자리씩 수정하기 위해서는 Int -> String으로 변환해주는 별도의 과정이 필요했다. 이외에는 기존의 BFS동작 방식과 큰 차이가 없었다.

코드

import math, copy
from collections import deque


def prime_check(n):  # n값이 소수인지 확인
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return 0
    return 1


def bfs(A, B):
    answer = 0
    # 한자리 값을 다루기 위해서 int -> string 변환

    q = deque([[list(str(A)), 0]])
    visited = {A}

    while True:
        val, cnt = q.popleft()
        if int("".join(map(str,val))) == B:
            return cnt
        else:
            for i in range(4):  # 각자리 변환
                for j in range(10):  # 변환 값
                    if val[i] == str(j):
                        continue
                    else:
                        temp = copy.deepcopy(val)
                        temp[i] = str(j)  # 값 변환
                        temp_value = int("".join(map(str, temp)))
                        if temp_value not in visited and temp_value >= 1000 and prime_check(temp_value):  # 조건 확인
                            visited.add(temp_value)
                            q.append([temp, cnt + 1])


if __name__ == "__main__":

    T = int(input())
    for _ in range(T):
        A, B = map(int, input().split())
        print(bfs(A, B))