Easy is Perfect

[백준] 1963번 python 풀이 _ 소수 경로

  • melonicedlatte
  • Jan 15, 2018


소수 경로 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB35361860133953.453%

문제

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

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

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

입력

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

출력

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

예제 입력 

3
1033 8179
1373 8017
1033 1033

예제 출력 

6
7
0

힌트

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 G번

  • 문제의 오타를 찾은 사람: waylight3

알고리즘 분류




문제분석

생각보다는 오답은 없이 잘 풀렸으나, 집중을 잘 하지 못하고 풀어서 시간이 너무 많이 걸렸다.
지금까지 주로 문제를 풀다 보면 재귀로 풀면 시간이 너무 많이 걸려서, 재귀 함수가 아닌 BFS를 사용해보았다. 

복잡도는 정확하지 않지만 직접 계산해보았다. (틀린점이 있으면 메일로 알려주세요!! )
하나의 소수에서 최대 k개의 자식 소수가 나온다고 가정해보자. ( 한 자리 숫자만 바꿨을 때, 소수인 수 )
그러면 하나의 자식 소수에서는 k개가 나오는데, 하나는 부모에 있기 때문에, k-1개의 자식 소수가 나올 것이다. 
이와 같은 식으로 1씩 감소하게 되면, BFS에 들어가는 최대  k + k*(k-1)+ ..... + k! 이 되게 된다. 

[높이 1] k
[높이 2] k*(k-1)
......
[높이 k] k!

총 시간 복잡도는 O(k!) 이고, k가 10 이라고 가정하면 약 3628800 정도의 값이 나온다. 
테스트 해보면 통상 6개 정도의 소수가 나오는 것 같다. (6! = 320 이기 때문에 큰 숫자는 아니다. )

위 식이 맞게 구해진 식이라면 자리수가 4 자리 이상이면 기하급수적으로 느려질 것 같다.
속도를 빠르게 하기 위해서 visited 딕셔너리를 사용하여, 방문 했던 노드의 경우에는 연산을 하지 않게 하여 추가적으로 
속도를 줄였다. 
 


정답

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import math
 
# global variables
mainQueue = [] 
visited = {}
depth = 0
 
# if num is Sosu return True else False
def isSosu(num):
    for i in range( 1,  int(math.sqrt(num))+1 ):
        if i == 1 :
            continue
        if num % i == 0 :
            return False
    return True
 
# if push number and index, make that index area number 0 
def makeOneNumberZero(num, index):
    _sub_num = 0 
    for i in range(4):
        if i == index:
            continue
        else :
            _sub_num += ((num / pow(10, i)) % 10 ) *  pow(10, i)
    return _sub_num
 
# one round of BFS
def oneRound(numA, numB):
    global depth
    global mainQueue
    subQueue = []
    depth += 1 
    
    # pop value of Queue while mainQueue doesn't have any element
    while len(mainQueue) > 0 :
        popedData = mainQueue.pop(0)
        
        # search one node's child 
        for i in range(4):
            subNum = makeOneNumberZero(popedData, i)
            for k in range(10):
                changedNum = k * pow(10, i) + subNum
                if changedNum != numA and changedNum > 1000 and isSosu(changedNum) == True:
                    # if two num is equal, return depth 
                    if changedNum == numB:
                        return depth
                    # if that number is already visited, skip! 
                    elif changedNum in visited.keys():
                        continue
                    else :
                        # make visited site 
                        visited[changedNum] = 1
                        subQueue.append(changedNum)
                    
    return subQueue
  
    
#  find minimum depth                   
def findMinChangeNum(numA , numB):
    global mainQueue
    
    # if numA and num B is equal when starting time, return 0 
    if numA == numB :
        print '0'
        return
    
    while True:
        # get one Round return value 
        answer = oneRound(numA, numB)
        
        # if answer is integer , it is depth!
        if type(answer) == int:
            print answer 
            return
        else :
            # if answer is [] , there is no next number
            if answer == [] :
                print 'Impossible'
                return
            # mainQueue change and ready to next Round
            else : 
                mainQueue = answer
 
 
# main is start!! 
input_text = raw_input().strip('\r').strip('\n').split(' ')
total_num = int(input_text[0]) 
 
for i in range(total_num):
    input_text = raw_input().strip('\r').strip('\n').split(' ')
    
    mainQueue = [ int(input_text[0]) ]
    depth = 0 
    visited = {}
    
    findMinChangeNum( int(input_text[0]),  int(input_text[1]) ) 
cs







Search