소수 경로

출처 : 백준 #1963

시간 제한	메모리 제한
2초	256MB

---

문제

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

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

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

---

입력

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

---

출력

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

---

입출력 예시

예제 입력 1

3
1033 8179
1373 8017
1033 1033

예제 출력 1

6
7
0

---

풀이

생각 및 풀이 설명

• 내가 놓친 point
  • 주어진 두 소수는 항상 오름차순으로 주어지는 것이 아니다.
  • 주어진 두 소수의 범위를 벗어난 소수를 들렀다가 가는 경우가 존재한다.
    • 따라서 prime_list의 범위를 1000이상 10000미만의 소수로 정하였다.
  • 만약 소수 이외의 수가 들어오면 Impossible을 출력해야한다.
    • 허나 문제의 조건은 소수만 입력된다고 했으므로 필요없는 부분이다.
• 문제 주요 point
  • 1. 우선 prime_list에 4자리 소수를 모두 넣는다.
  • 2. 주어진 두 소수가 오름차순이라면 그대로 두고, 내림차순이라면 prime_list를 역순으로 정렬한다. (이유 : 뒤에서부터 탐색해야 하므로)
  • 3. 만약 prime_list를 돌면서 그 안의 소수가 방문하지 않은 소수이고, 큐에서 꺼낸 소수와 1자리만 숫자가 다르다면 바뀐 횟수(number)를 1 더해주고
       큐에 다시 집어 넣는다.(사실상 BFS)
  • 4. 만약 도중 목표 소수와 값이 같다면 멈춘다.

python code

# 백준 1963번 소수 경로
from sys import stdin
from collections import deque
input = stdin.readline
t = int(input())
answer = []
for _ in range(t):
    n, m = map(int, input().split())
    flag = True
    if n == m:  # 두 수가 같은 경우
        answer.append(0)
        flag = False
        continue
        
    visited = [False] * (10000) 
    prime_list = []
    q = deque()
    q.append((n, 0))
    visited[n] = True
    prime_list = []
    # 먼저 소수만 뽑아내기
    for t in range(1000, 10000):    
        # 처음에 범위를 주어진 소수 내로 정해서 틀림 
        # (4자리수 소수면 다 가능토록 해야함)
        j = 2
        pr = True
        while j * j <= t:
            if t % j == 0:
                pr = False
                break
            else:
                j += 1
        if pr:
            prime_list.append(t)
    if n > m:   # 첫번째 소수가 더 큰 경우
        prime_list.sort(reverse=True)
    while q and flag:
        start, number = q.popleft()
        for test in prime_list:
            count = 0
            if visited[test] == False:
                for x in range(4):
                    if str(test)[x] != str(start)[x]:
                        count += 1
                    if count > 1:
                        break
                if count == 1:
                    q.append((test, number+1))
                    visited[test] = True
                    if test == m:
                        answer.append((number+1))
                        flag = False
                        break
    if flag == True:
        answer.append("Impossible")

for i in range(len(answer)):
    print(answer[i])
# 1
# 8179 1733
# 반대인 경우 index error