[Python]14395번.4연산(그래프, BFS)

14395번: 4연산

💡문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

풀이💬

import sys
from collections import deque

s, t = map(int, input().split())
queue = deque()
check = set()

queue.append((s, ''))
check.add(s)

max = 10e9

if s == t:
    print(0)
else:
    res = -1
    
    while queue:
        V, S = queue.popleft()
        if V == t:
            res = S
            print(S)
            exit(0)

        V2 = V * V
        if 0 <= V2 <= max and V2 not in check:
            queue.append((V2, S + '*'))
            check.add(V2)

        V2 = V + V
        if 0 <= V2 <= max and V2 not in check:
            queue.append((V2, S + '+'))
            check.add(V2)

        V2 = 1
        if V2 not in check:
            queue.append((V2, S + '/'))
            check.add(V2)
    print(res)

 

• check 라는 변수는 이미 방문한 값들의 집합을 나타낸다. set 집합 자료형은 특정 값이 이미 집합에 있는지 확인한다.(중복 처리 방지)
• 큐에 추가되는 값은 (V, S)쌍으로 저장이되는데 'V'는 형재 값이고 'S'는 현재까지의 연산을 나타낸다. 
• 큐에 반복해서 저장하고 원하는 t값이 나오면 return된다.