https://www.acmicpc.net/problem/1963
1963번: 소수 경로
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금
www.acmicpc.net
문제
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
- “이제 슬슬 비번 바꿀 때도 됐잖아”
- “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
- “그럼 8179로 해”
- “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
- “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
- “귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
입력
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
출력
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
너비우선탐색(BFS)로 0000 각 자리 중 하나를 0~9로 바꾸어보고, 해당 숫자가 소수이면 que에 추가하였다.
이 때, 소수를 판별하는 2가지의 알고리즘으로 문제를 풀어보았다.
1. 특정 N이 주어질 때, 2~루트 N까지 나누어지지 않는 숫자는 소수 임을 이용한 풀이
: 바꿔본 숫자가 소수인지 매번 계산을 해줘야 하기 때문에, 시간 소요가 크다.
import sys, math, heapq
def chkPrime(num):
global set
num = int(''.join(num))
sqrt = int(math.sqrt(num))
if num in set:
return False
set.append(num)
for r in range(2, sqrt+1):
if num % r == 0:
return False
return True
### MAIN
N = int(sys.stdin.readline())
for _ in range(N):
num1, num2 = sys.stdin.readline().strip().split()
que, set = [], []
res = "Impossible"
heapq.heappush(que, (0, list(num1), -1))
for r in range(4):
for i in range(0,10):
chgNum = list(num1)
if (r==0 and i == 0) or chgNum[r] == str(i):
continue
chgNum[r] = str(i)
if(chkPrime(chgNum)): # 소수가 맞으면
# print(chgNum)
heapq.heappush(que, (1, chgNum, r)) # 변경횟수, 바뀐 소수, 바뀐 인덱스
while que:
cnt, before, idx = heapq.heappop(que)
if ''.join(before) == num2:
res = cnt
break
for r in range(4):
if r == idx:
continue
for i in range(0, 10):
if r==0 and i == 0:
continue
chgNum = list(before)
chgNum[r] = str(i)
if(chkPrime(chgNum)): # 소수가 맞으면
heapq.heappush(que, (cnt+1, chgNum, r)) # 변경횟수, 바뀐 소수, 바뀐 인덱스
print(res)
2. 에라토스테네스의 체
: 소수를 하나 선택. 소수의 배수는 모두 소수가 아님을 이용하여 2~N까지 소수 여부를 미리 구해놓는 방법.
추가로 vi배열을 만들어 이미 바꿔서 만들었던 소수는 다시 선택되지 않도록 하였다.
import sys, heapq
def getPrime(arr): # 9999까지 미리 소수여부를 저장
for i in range(2,10000):
if arr[i]: #소수이면, r의 배수는 모두 소수가 아님
for j in range(i*2, 10000, i):
arr[j] = False
for i in range(1000): # 1000보다 작으면 안됨.
arr[i] = False
### MAIN
N = int(sys.stdin.readline())
arr = [True for _ in range(10000)] # 0~999까지 소수 여부를 저장하는 배열
getPrime(arr)
for _ in range(N):
num1, num2 = sys.stdin.readline().strip().split()
vi = [False for _ in range(10000)]
que = []
heapq.heappush(que, (0, num1))
res = 'Impossible'
while que:
cnt, num = heapq.heappop(que)
if ''.join(num) == num2:
res = cnt
break;
for i in range(4):
for j in range(10):
chgNum = list(num)
chgNum[i] = str(j)
intNum = int(''.join(chgNum))
if arr[intNum] and not vi[intNum]: # 소수이고 방문하지 않은 경우,
heapq.heappush(que, (cnt+1, chgNum))
vi[intNum] = True
print(res)
두 가지 풀이 중에서는 두번째 방법이 월등하게 속도가 빨랐다.
관련 게시글: 2021.05.10 - [Algorithm/알고리즘] - 소수 판별 알고리즘 (에라토스테네스의 체)
'Algorithm > 문제풀이' 카테고리의 다른 글
[Python][프로그래머스] 42888_오픈채팅방 (0) | 2021.08.28 |
---|---|
[Python][프로그래머스] 12979_기지국 설치 (0) | 2021.08.22 |
[Python][백준] 18113_그르다 김가놈 (0) | 2021.08.10 |
[Python][프로그래머스] 49189_가장 먼 노드 (0) | 2021.08.09 |
[Python][프로그래머스] 42842_카펫 (0) | 2021.08.09 |