[Python] 17394번 핑거 스냅

 

 

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

17394번: 핑거 스냅

---

 

22/11/18

 

 

BFS와 에라토스테네스의 체를 섞은 독특한 문제로, 두 알고리즘을 모두 알고 있다면 어렵지 않게 해결할 수 있는 문제이다.

 

특히, 이 문제는 1697번 숨바꼭질 문제와 같은 방식으로 방문처리를 하기 때문에 1697번을 해결했었다면 이 문제 또한 쉽게 해결할 수 있을 것이다.

---

 

문제 접근 방식:

 

 

먼저 목표 범위인 $A$와 $B$의 범위를 보면 $2 \leq A \leq B \leq 100,000$이라는 사실을 알 수 있다.

 

이를 통해, $100,000$까지 에라토스테네스의 체를 돌린다.

 

이후 BFS함수를 정의해 주는데, 이때, 목표 범위 안에 있는 소수에 도달하면 되기 때문에 이 목표 범위 안에 있는 소수를 모아놓은 셋, $goal$을 만들어준다.

 

만약 $goal$에 원소가 있다면 생명체 수의 변화량에 $+1$과 $-1$이 있기 때문에 어떻게든 탐색을 통해 도달할 수 있으므로 BFS를 진행하고, 만약 $goal$에 원소가 존재하지 않으면 탐색을 통해 도달할 수 없으므로 $-1$을 리턴해준다.

 

$N$의 범위가 $1,000,000$까지로 매우 크기 때문에, BFS를 진행할 때에는 $N$의 크기만큼의 해당되는 배열을 선언하여 방문처리를 하는 것이 아닌, set을 통해 방문처리를 해주었다.

 

주의해야 될 점은, $0$보다 밑으로 갈 수 없다는 점이다.

 

때문에 BFS를 진행할때 만약 현재 숫자가 $0$이라면 for문을 돌리지 않음으로써 시간을 단축했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17394번 핑거 스냅
# 수학, 정수론, 소수 판정, 에라토스테네스의 체, 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
에테체로 돌린 뒤 BFS로 가자
'''
import sys
from collections import deque
input = sys.stdin.readline

sieve = [0, 1]*50001
sieve[0], sieve[1], sieve[2] = 0, 0, 1
for i in range(3, 318):
    if sieve[i]:
        for j in range(2*i, 100001, i):
            sieve[j] = 0
def BFS(start, A, B):
    goal = set(i for i in range(A, B+1) if sieve[i])
    if goal:
        queue = deque()
        queue.append((start, 0))
        visited = set()
        visited.add(start)
        while queue:
            number, time = queue.popleft()
            if number in goal:
                return time
            else:
                next_num_arr = [number//2, number//3, number-1, number+1]
                if number == 0:
                    continue
                for next_num in next_num_arr:
                    if next_num not in visited:
                        visited.add(next_num)
                        queue.append((next_num, time+1))
    else:
        return -1
        
T = int(input())
for _ in range(T):
    start, A, B = map(int, input().rstrip().split())
    print(BFS(start, A, B))