[백준] 1963번 소수 경로 - Python / 알고리즘 중급 1/3 - BFS (연습)

---

---

---

💡 문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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. 먼저 9999까지 모든 소수를 구해 prime 리스트에 bool 형으로 저장한다. (소수면 1, 아니면 0)
2. 이후 입력받은 숫자에 대해 1, 2, 3, 4번째 자리수를 따로 분리한 뒤, 이 숫자들을 0~9까지의 수로 교체한다.
3. 위 2번에서 바꾼 수가 소수이고, 방문하지 않은 수이며, 999보다 큰 수라면(4자리수라면) 한자리만 바뀐 소수이므로 원하는 수를 찾을 때까지 bfs를 돌린다.
4. 이후, 목표 숫자를 찾았다면 이때까지 바꾼 횟수(cnt)를, bfs 함수가 끝났음에도 원하는 수를 찾지 못했다면 'Impossible'을 출력한다.

---

📒 코드

import sys
from collections import deque
input = sys.stdin.readline

def seive_of_eratosthenes(n):
    is_prime = [1 for _ in range(n + 1)]
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i**2, n + 1, i):
                is_prime[j] = 0
    return is_prime[:]
prime = seive_of_eratosthenes(10000)

def bfs(start):
    q = deque()
    q.append((start, 0))

    while q:
        num, cnt = q.popleft()

        if num == b:
            return cnt
        
        num1 = num // 1000
        num2 = num // 100 % 10
        num3 = num // 10 % 10
        num4 = num % 10
        
        for i in range(10):
            next1 = i * 1000 + num2 * 100 + num3 * 10 + num4
            next2 = num1 * 1000 + i * 100 + num3 * 10 + num4
            next3 = num1 * 1000 + num2 * 100 + i * 10 + num4
            next4 = num1 * 1000 + num2 * 100 + num3 * 10 + i

            if next1 > 999 and prime[next1] == 1 and visited[next1] == 0:
                visited[next1] = 1
                q.append((next1, cnt + 1))
            if next2 > 999 and prime[next2] == 1 and visited[next2] == 0:
                visited[next2] = 1
                q.append((next2, cnt + 1))
            if next3 > 999 and prime[next3] == 1 and visited[next3] == 0:
                visited[next3] = 1
                q.append((next3, cnt + 1))
            if next4 > 999 and prime[next4] == 1 and visited[next4] == 0:
                visited[next4] = 1
                q.append((next4, cnt + 1))
    return 'Impossible'

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    visited = [0 for _ in range(10000)]

    print(bfs(a))

---

💭 후기

오랜만에 쉬운 문제라서 가벼운 마음으로 풀었던 문제였다.

---

🔗 문제 출처

https://www.acmicpc.net/problem/1963

---