[BFS] 백준 14395 : 4연산 - 파이썬 Python

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

14395번: 4연산

 

생각하기

최소의 변환을 찾으면 되는 문제이기 때문에 BFS로 접근해야겠다고 생각

 

평소처럼 visited 배열(list)을 통해서 방문 여부를 검사려고하니, 메모리 문제가 발생

-> 각 연산의 특성을 잘 생각해보면 모든 10^9숫자를 다 사용하지는 않음

 

• 뺄셈을 만나면 S - S 로 0이 되므로 사실상 끝
• 나눗셈을 만나면 S / S 로 1이 되므로 사실상 2의 배수가 된다

S^a * 2^b 형태이므로 10^9가 다 사용되지는 않을 예정

 

이런 경우 모든 수를 배열로 선언하는 것 보다는 Hash Table 방식을 사용하는 set()을 visited로 선언하여 

탐색의 시간 복잡도를 O(1)로 축소해주는 것이 좋다

 

경로를 나타내기 위해서는 q에 append 할 때 마다 연산자들을 string으로 넘겨주면 된다

 

 

구현하기

visited = set()

• set으로 구현 - O(1)의 시간 복잡도를 가지고 찾을 수 있음
• 10^9 크기의 배열을 사용하지 않아도 됨

q = deque()

• (연산의 결과 숫자, 여태까지 연산해온 연산자들을 concat한 string)을 element로 append / popleft 함
• q가 empty가 될때까지 while문을 돈다는 것은 결국 t로 숫자 변환을 실패했다는 뜻

 

from collections import deque
from re import T

s, t = map(int, input().split())


if s == t:
    print(0)

else:

    q = deque()
    visited = set()
    q.append((s, ''))


    while q:
        num, op_str = q.popleft()
        if num == t:
            print(op_str)
            exit(0)

        if 0<= num*num <= 10**9 and (num*num not in visited):
            visited.add(num*num)
            q.append((num*num, op_str+'*'))

        if 0<= num*2 <= 10**9 and (num*2 not in visited):
            visited.add(num*2)
            q.append((num*2, op_str+'+'))

        if 0 not in visited:
            visited.add(0)
            q.append((0, op_str+'-'))
    
        if num != 0 and (1 not in visited):
            visited.add(1)
            q.append((1, op_str+'/'))

    print(-1)