[백준] 14395번 4연산

💡문제접근

• BFS를 써야하는 문제라고 생각하고 바로 풀이에 들어갔다.
• 처음엔 방문 여부를 따지는 배열 visited를 리스트로 만들었는데 그렇게 된다면 최대 1e9까지의 길이를 가진 배열을 만들어야하므로 메모리 초과가 발생할 것 같아 중복을 제거하는 set을 사용했다.

💡코드(메모리 : 34176KB, 시간 : 76ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(start, result):
    queue = deque()
    if s == t:
        return 0
    queue.append((start, ""))
    visited.add(start)
    while queue:
        v, op = queue.popleft()
        if v == t:
            return op

        if v * v <= 1e9 and v * v not in visited:
            visited.add(v * v)
            queue.append((v * v, op + "*"))

        if v + v <= 1e9 and v + v not in visited:
            visited.add(v + v)
            queue.append((v + v, op + "+"))

        if 0 not in visited:
            visited.add(0)
            queue.append((v - v, op + "-"))

        if s != 0 and s >= 1 and 1 not in visited:
            visited.add(1)
            queue.append((v // v, op + "/"))
    return -1


s, t = map(int, input().strip().split())
visited = set()
print(BFS(s, ""))

💡소요시간 : 19m