반응형
문제
https://www.acmicpc.net/problem/1963
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
- “이제 슬슬 비번 바꿀 때도 됐잖아”
- “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
- “그럼 8179로 해”
- “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
- “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
- “귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
입력
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
출력
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
코드
import sys, math
from collections import deque
input=sys.stdin.readline
def checkPrime():
for i in range(2, 100):
if prime[i]==True:
for j in range(2*i, 10000, i):
prime[j]=False
def bfs():
q=deque()
q.append([start, 0])
visited=[0 for i in range(10000)]
visited[start]=1
while q:
x, cnt=q.popleft()
strx=str(x)
if x==end: return cnt
for i in range(4):
for j in range(10):
tmp=int(strx[:i]+ str(j)+strx[i+1:])
if tmp>=1000 and prime[tmp]==True and visited[tmp]==0:
visited[tmp]=1
q.append([tmp, cnt+1])
T=int(input())
prime=[True for i in range(10000)]
checkPrime()
for i in range(T):
start, end=map(int, input().split())
result=bfs()
if result==None: print("Impossible")
else: print(result)
문제 해결
BFS와 소수판별을 같이 해야하는 문제이다. 파이썬의 문자열과 정수형 변환을 적절히 이용하여 방문판단후 횟수를 파악하여 코드를 작성하였다. 난이도 매우 높은 문제
반응형
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 1987번: 알파벳 - [Python/파이썬] (1) | 2023.04.14 |
---|---|
[백준] 1978번: 소수 찾기- [Python/파이썬] (0) | 2023.04.14 |
[백준] 1934번: 최소공배수 - [Python/파이썬] (0) | 2023.04.14 |
[백준] 1932번: 정수 삼각형 - [Python/파이썬] (0) | 2023.04.14 |
[백준] 1931번: 회의실 배정 - [Python/파이썬] (0) | 2023.04.14 |