문제 설명

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

“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력 조건

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

출력 조건

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

전체 코드

import math
import sys
from collections import deque

test_case = int(sys.stdin.readline().rstrip())


def is_prime(num_list: tuple) -> bool:
    num = num_list[0] * 1000 + num_list[1] * 100 + num_list[2] * 10 + num_list[3]
    # 1 이하면 소수가 아님
    if num <= 1:
        return False
    # O(n^1/2)
    for e in range(2, int(math.sqrt(num)) + 1):
        # 나누어 떨어지는 게 있으면 소수가 아니다.
        if num % e == 0:
            return False
    # 나누어 떨어지는 게 없으면 소수다.
    return True


def get_change_count(origin: list[int], destination: list[int]) -> int:
    queue = deque()
    queue.append((origin[0], origin[1], origin[2], origin[3], 0))

    # 이전에 만든 수였는지 확인한다.
    visited = set()
    visited.add((origin[0], origin[1], origin[2], origin[3]))

    while queue:
        # a,b,c,d는 첫 째 자릿수 부터 넷 째 자릿수를 나타낸다. count는 변경 횟수를 뜻한다.
        a, b, c, d, count = queue.popleft()

        # bfs 특성 상, 가장 먼저 목적지에 도착하면 최소 거리다.
        if a == destination[0] and b == destination[1] and c == destination[2] and d == destination[3]:
            return count

        # 첫째 자릿수는 1부터 9까지만 가능하다. 그 외 자릿수는 0부터 9까지 모두 가능하다.
        for e in range(1, 10):
            if e != a:
                # 새로 만든 수
                new_number = (e, b, c, d)
                # 새로 만든 수가 만든 적이 없고(o(1)) 소수라면(o(n)), 큐에 담는다.
                if new_number not in visited and is_prime(new_number):
                    visited.add((e, b, c, d))
                    queue.append((e, b, c, d, count + 1))

        for e in range(0, 10):
            if e != b:
                # 새로 만든 수
                new_number = (a, e, c, d)
                # 새로 만든 수가 만든 적이 없고(o(1)) 소수라면(o(n)), 큐에 담는다.
                if new_number not in visited and is_prime(new_number):
                    visited.add((a, e, c, d))
                    queue.append((a, e, c, d, count + 1))

        for e in range(0, 10):
            if e != c:
                # 새로 만든 수
                new_number = (a, b, e, d)
                # 새로 만든 수가 만든 적이 없고(o(1)) 소수라면(o(n)), 큐에 담는다.
                if new_number not in visited and is_prime(new_number):
                    visited.add((a, b, e, d))
                    queue.append((a, b, e, d, count + 1))

        for e in range(0, 10):
            if e != d:
                # 새로 만든 수
                new_number = (a, b, c, e)
                # 새로 만든 수가 만든 적이 없고(o(1)) 소수라면(o(n)), 큐에 담는다.
                if new_number not in visited and is_prime(new_number):
                    visited.add((a, b, c, e))
                    queue.append((a, b, c, e, count + 1))

    return -1


answer = []
for i in range(test_case):
    one, other = list(map(str, sys.stdin.readline().split()))
    one = [int(elem) for elem in one]
    other = [int(elem) for elem in other]

    min_count = get_change_count(one, other)
    if min_count == -1:
        answer.append("Impossible")
    else:
        answer.append(min_count)

for elem in answer:
    print(elem)

해설

시도했던 풀이

처음엔 자릿수가 최대 4이고, 소수가 아닌 경우에는 더 이상 진행하지 않으므로 백트래킹 풀이를 해야하는 줄 알았다.
하지만 실제 코딩에 들어가고 나서 깨달은 것은 (사실 코딩하기 전에 깨달아야 했다.), 기저 조건을 어떻게 설정하지? 라는 것이였다.

문제에 나온 예 1033 1733 3733 3739 3779 8779 8179의 경우 2번째 자릿수->1번째 자릿수->4번째 자릿수->3번째 자릿수...로 되어 있다. 즉, 자릿수로 기저 조건을 정할 수 없다. (계속 자릿수가 뒤로 진행되는 게 아니라 앞 뒤 왔다갔다 할 수 있기 때문이다.)다른 변수로도 기저 조건을 만들만한 게 보이지 않았다. 재귀에서 기저 조건을 만들지 못한다면 무한 루프에 빠지게 되므로, 이 문제는 재귀로 풀어선 안되는 문제였다.

정답인 풀이

그래서 숫자 (예시로 1033) 하나에 대해 만들 수 있는 상태들을 먼저 고려해봤다.

1033의 경우, 첫 번째 자릿수를 바꾼다면 2033,3033,...9033이 될 수 있다.
두 번째 자릿수를 바꾼다면, 1133,1233,...1933.
세 번째 자릿수를 바꾼다면, 1013,1023,...1093.
네 번째 자릿수를 바꾼다면, 1030,1031,...1039다.

이를 그림으로 표현해 보았다.

그림으로 그려보니, 그래프의 4방향 BFS가 떠올랐다.

방문 기록을 저장(visited)하는 BFS를 활용한다면, 이전에 방문했던 상태는 다시 방문하지 않는다. 따라서 Queue 는 결국에 비게 된다. 즉, 무한 루프가 발생할 수가 없다.

그리고 DFS 대신 BFS를 활용한 이유는 최단 거리 보장이라는 특성 때문이다.

두 방식 모두 노드들을 탐색하는 방법이다. 하지만 BFS는 가장 먼저 목적 상태에 도달한 노드의 거리가 최단이다라는 특성이 있다. DFS는 그러한 특성이 없어서 빠르게 최단 거리를 찾지 못하고 계속 헤맬 수가 있다.

즉, 이 예시를 그래프 문제로 치환한다면 1033이라는 출발 상태를 8079라는 목적 상태로 도달하기 위해 바꿔야 하는 최소 비용을 묻는 문제라 할 수 있다.