[Algorithm] BaekJoon : 1963. 소수 경로 by Python

[문제 바로가기] https://www.acmicpc.net/problem/23288

23288번: 주사위 굴리기 2

 

📌 문제 설명

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

 

---

💡 문제 풀이

DP + BFS로 해결한 문제!

테스트케이스 수가 많을수록 매번 소수를 구하는것이 비효율적이라고 판단하여, 소수는 '에라토스테네스의 체'를 이용하여 미리 구하였다.

 

이후 '비밀번호를 한 번에 한 자리 밖에 못 바꾼다'는 조건을 BFS를 이용하여 탐색하였다.

주요 진행과정은 아래와 같다.

1. 각 자릿수를 0 ~ 9로 바꾼 후 그 숫자가 1000이상 9999이하 인지 판단한다.

2. 1000이상 9999이하이면 해당 숫자가 소수이면서 이전에 탐색한 적이 없는지 확인한다.

3. 1, 2조건을 모두 만족하면 큐(queue)에 해당 숫자를 담고 visited값을 이전 탐색 visited값+1로 최신화시켜준다.

 

 

코드는 다음과 같다.

import sys
from collections import deque
sys.stdin = open('백준1963. 소수 경로.txt', 'r')

def bfs():
    global start, end, answer
    # 비밀번호 범위가 1000 ~ 9999 이므로 배열의 길이는 9000
    visited = [0] * 9000
    visited[int(start)-1000] = 1
    queue = deque([start])
    while queue:
        s = queue.popleft()
        # 각 자릿수에 대해서 0~9로 바꾸며 확인
        for i in '0123456789':
            test = [i+s[1:], s[0]+i + s[2:], s[:2]+i + s[-1], s[:3]+i]
            for t in test:
                num = int(t)
                # 1000이상 9999이하이고 탐색한적이 없으며 소수여야 함
                if 1000 <= num <= 9999 and not visited[num-1000] and not DP[num]:
                    if t == end:
                        answer = visited[int(s)-1000]
                        return
                    visited[num-1000] = visited[int(s)-1000]+1
                    queue.append(t)

DP = [0] * 10000
for i in range(2, int(len(DP) ** (0.5))):
    if not DP[i]:
        for j in range(i*2, 10000, i):
            DP[j] = 1
T = int(input())
for _ in range(T):
    answer = -1
    start, end = input().split()
    if start == end:
        answer = 0
    bfs()
    print("Impossible") if answer == -1 else print(answer)

---