백준 14395 : 4연산 (Python)

본문 링크

from collections import deque
S,T=map(int,input().split())

visit=set()
visit.add(S)

if T==S:
    print(0)
    exit(0)

def BFS(start):
    deq=deque()
    deq.append([start,""])

    while deq:
        x,String=deq.popleft()
        if x==T:
            return String

        if x*x<=T and x*x not in visit:
            deq.append([x*x,String+"*"])
            visit.add(x*x)
        if x+x<=T and x+x not in visit:
            deq.append([x+x, String+"+"])
        if x//x not in visit:
            deq.append([x//x , String+"/"])

answer=BFS(S)
if answer==None:
    print(-1)
else:
    print(answer)

📌 어떻게 접근할 것인가?

BFS 를 통해 탐색하였다.
다만 중요한것은 $s$ 와 $t$ 의 범위가 $(1 ≤ s, t ≤ 10^9)$ 이라는 점이다.
즉 중복체크를 위해 visit 방문배열을 만들면 메모리 초과가 발생한다.

따라서 $set$ 을 사용하기로 했다.

$set$ 은 if a in b 를 실행할시 $O(1)$ ~ $O(N)$ 의 시간 복잡도가 든다. $remove$ 또한 마찬가지다.
오늘 이문제를 풀면서 처음안 사실인데 다음에 $BFS$ 에서 중복체크를 할때 $set$ 을 적극적으로 활용해야겠다.

이렇게 시간복잡도가 작은 이유는 해쉬테이블을 사용해서 그런데 자세한 내용은
자료구조의 이해 , TimeComplexity-Python 이 글을 참조하면 좋을것이다.