[Python][백준] 1963_소수 경로

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

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을 출력한다.

---

너비우선탐색(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/알고리즘] - 소수 판별 알고리즘 (에라토스테네스의 체)