백준 1963번 - 소수 경로

출처 : 1963번: 소수 경로 (acmicpc.net)

1963번: 소수 경로

 

소수 경로 성공출처다국어분류

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

256 MB

10131

5587

3965

55.501%

문제

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

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

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

입력

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

출력

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

 

---

[ 문제 설명 ]

 

그림으로 설명하겠습니다.

 

그림 1 - 문제 풀이 아이디어

그림 2 - 문제 풀이 아이디어

그림 3 - 문제 풀이 아이디어

그림 4 - 문제 풀이 아이디어

---

[ 코드 ]

 

import copy
from collections import deque


# 기본적인 소수 판별 방법(2부터 n-1까지 돌려보기)
def is_prime_number(x):
    # 2부터 (x - 1)까지의 모든 수를 확인
    for i in range(2, x):
        # x가 해당 수로 나누어떨어지면
        if x % i == 0:
            return False
    return True


def bfs(a, b):

    q = deque([[list(str(a)), 0]])
    # print(q)
    visited = {a}

    while True:
        val, cnt = q.popleft()
        if int("".join(map(str, val))) == b:
            return cnt
        else:
            for i in range(4):
                for j in range(10):
                    if val[i] == str(j):  # 같은 숫자는 바꾸는게 의미가 없으므로
                        continue
                    else:
                        temp = copy.deepcopy(val)
                        temp[i] = str(j)  # 숫자 바꾸기
                        temp_value = int("".join(map(str, temp)))
                        # 조건에 맞게 확인
                        if temp_value not in visited and temp_value >= 1000 and is_prime_number(temp_value):
                            visited.add(temp_value)
                            q.append([temp, cnt + 1])


TestCase = int(input())
for _ in range(TestCase):
    a, b = map(int, input().split())
    print(bfs(a, b))

 

---

후기

 

음...

그냥 그렇네요 이번 문제는