[Python] 14395번 4연산

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

14395번: 4연산

---

 

24/01/12

 

 

단순한 BFS문제다.

---

 

문제 접근 방식:

 

 

BFS문제다. 다만 $10^9$짜리 배열을 만들어서 방문 처리를 하기가 곤란했기 때문에, 방문 처리는 딕셔너리로 해결했다.

 

키-값 쌍이 존재하는 경우에는 방문 처리가 되어있다고 간주하고, 키는 정수, 값은 그때의 방법을 담은 문자열로 구현했다.

 

숫자 범위가 큶에도 BFS가 잘 작동하고 바꿀 수 없는 경우를 빠르게 판단할 수 있는 이유를 나름대로 생각했다.

 

일단 빼기 연산은 작동을 하지 않고, $/$연산은 $1$로 밖에 만들지 못하기 때문에, 정수 $s$보다 작게 만드는 방법은 매우 한정될 것이라고 생각했다.

 

실제로도 $/$연산을 사용하여 $1$을 만든 다음에 숫자를 계속 늘린다고 한다면, 가장 적은 차이가 나게 끔 $+$연산 만을 사용하여 늘려도 $1, 2, 4, 8, \cdots$ 즉, $2$의 거듭제곱 수로 늘어나기 때문에 금세 제한을 넘어버리게 될 것이다.

 

따라서 충분히 시간 내에 돌아갈 것이라고 예상할 수 있다.

   

---

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

# 14395번 4연산
# BFS
import sys
input = sys.stdin.readline
from collections import deque

LIM = 1_000_000_000
def main():
    s, t = map(int, input().rstrip().split())
    if s == t:
        print(0)
        return
    visited = dict()
    visited[s] = ''
    queue = deque()
    queue.append(s)
    while queue:
        num = queue.popleft()
        if num == t:
            print(visited[t])
            return
        if 1 <= num*num <= LIM and num*num not in visited:
            visited[num*num] = visited[num]+'*'
            queue.append(num*num)
        if 1 <= num+num <= LIM and num+num not in visited:
            visited[num+num] = visited[num]+'+'
            queue.append(num+num)
        if 1 <= num-num <= LIM and num-num not in visited:
            visited[num-num] = visited[num]+'-'
            queue.append(num-num)
        if num != 0 and 1 <= num//num <= LIM and num//num not in visited:
            visited[num//num] = visited[num]+'/'
            queue.append(num//num)
    if t in visited:
        print(visited[t])
    else:
        print(-1)
    return
main()