문제:

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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를 사용하는 문제다.

우선 네 자리 수인 모든 소수를 찾기 위해서 에라토스테네스의 체를 사용한다. 에라토스테네스의 체를 1부터 10000까지 적용을 한 뒤에 filter를 사용해 1000보다 큰 수들만 남기도록 한다.

 네 자리 소수를 모두 구한 뒤에는 bfs를 사용해서 기준이 되는 숫자와 네 자리 소수를 모두 비교해서 하나만 다른 경우에만 새 queue에 넣는 방식으로 진행한다. 이 때 중복 방문을 피하기 위해서 visited 배열을 사용한다. 만약 목적지 소수를 발견하면 bfs를 종료하고 answer를 출력하며, 만약 모든 소수를 방문해도 도달하지 못했다면 Impossible을 출력하게 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from collections import deque
import math
 
def check_sosu(s):
    for i in range(2,int(math.sqrt(s))+1):
        if not s%i:
            return 0
    return 1
 
def sosu():
    sosu_list = list(range(10001))
    sosu_list[1= 0
    for s in sosu_list:
        if sosu_list[s] and check_sosu(s):
            for j in range(s+s,10001,s):
                sosu_list[j]=0
    return list(set(sosu_list))
 
def change(a,b):
    count = 0
    for i,j in zip(str(a),str(b)):
        if i==j:
            count+=1
    if count==3:
        return 1
    else:
        return 0
 
= int(input())
sosu_list = sosu()
sosu_list = sorted(list(filter(lambda x: x >= 1000, sosu_list)))
 
for _ in range(T):
    start, end = map(int,input().split())
    visited = [0]*len(sosu_list)
    visited[sosu_list.index(start)]=1
    if start==end:
        print(0)
        continue
    queue = deque([start])
    answer = 0
    possible = False
    while not possible and queue:
        tmp = deque([])
        for q in queue:
            if q==end:
                possible = True
                break
            for i,s in enumerate(sosu_list):
                if not visited[i]:
                    if change(q,s):
                        tmp.append(s)
                        visited[i] = 1
        else:
            queue = tmp
            answer+=1
    if possible:
        print(answer)
    else:
        print("Impossible")
cs

문제링크:

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

 

1963번: 소수 경로

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2573. 빙산  (0) 2021.08.30
[BOJ]10942. 팰린드롬?  (0) 2021.08.26
[BOJ]1074. Z  (0) 2021.08.12
[BOJ]2108. 통계학  (0) 2021.08.05
[BOJ]2206. 벽 부수고 이동하기  (0) 2021.08.03

+ Recent posts