백준 14395번 4연산

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

실패이유: 구현실패

import collections
import sys

max_val = 10_0000_0000
given, target = map(int, input().split())

if given == target:         # 숫자가 같은 경우
    print(0)

visit = set()

queue = collections.deque()
queue.append((given, ''))
visit.add(given)

while queue:
    number, way = queue.popleft()

    if number == target:
        print(way)
        sys.exit()

    if number * number not in visit and number * number <= max_val:     # 곱하기 연산
        visit.add(number * number)
        queue.append((number * number, way + '*'))

    if number + number not in visit and number + number <= max_val:     # 더하기 연산
        visit.add(number + number)
        queue.append((number + number, way + '+'))

    if 1 not in visit:                                                  # 나누기 연산, 어떤수든지 1로 만든다.
        visit.add(1)
        queue.append((1, way + '/'))

print(-1)   # given 으로 target 을 만들 수 없는 경우

• 주어진 정수 범위가 1 ~ 10^9 라 너무 커서 BFS 로 어떤식으로 접근해야 할지 감이 안잡혔다.
• 문제에서 * 연산은 제곱 연산, + 연산은 2배 곱하는 연산, - 는 0으로 만드는 연산, / 는 1로 만드는 연산이다.
  • - 연산 같은 경우엔 쓸모가 없다.
  • x -> x^2 또는 x -> 2 * x 형태로의 변형만 가능하다.
  • 따라서 실제로 방문할 수 있는 노드는 많지 않다.
    
    
• 예를 들어 given 이 3인 경우 2^a * 3^b 의 노드들을 방문할 수 있다.
  • / 를 사용해 1로 만들고 + 연산을 통해 2^30 까지 방문할 수 있고 (방문할 수 있는 노드 약 30개)
  • 주어진 숫자가 3 인 경우 * 연산을 통해 3^20 까지 방문할 수 있다. (방문할 수 있는 노드 약 20개)
  • 따라서 총 방문할 수 있는 노드는 많아봐야 대략 30 * 20 = 600 개 정도이므로 BFS 로 문제를 풀 수 있다.
    
    
• 범위에 주의하며 문제를 푼다.
  • 1 <= s, t <= 10억

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43