백준: 14395 4연산

문제

14395번: 4연산

 

문제 풀이

 S가 주어질 때 S를 사칙연산(`*`, `+`, `-`, `/`)을 통해 T로 만드는 경우 사용한 연산자들을 출력하는 문제이다. 이 문제는 BFS를 통해 풀 수 있으며, `*`, `+`, `/`에 대해서만 경우의 수를 찾기 위해 가지를 뻣으면 된다. 왜냐하면 `-`의 경우 값이 빠지게 되므로 최소 연산 횟수를 벗어나기 때문이다.

 

 또한, 연산의 아스키코드 순서의 우선순위를 보장하기 위해, 가지를 뻗어 나갈 때 `*`, `+`, `/` 순으로 큐에 추가하면 순서를 보장할 수 있다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        num, result = q.popleft()

        if num == t:
            return result

        for op in ('*', '+', '/'):
            if op == '*':
                new_s = num * num
            elif op == '+':
                new_s = num + num
            else:
                new_s = 1

            if 0 <= new_s <= t and new_s not in visited:
                visited.add(new_s)
                q.append([new_s, result + op])
    return -1


if __name__ == '__main__':
    s, t = map(int, stdin.readline().split())
    visited = set()

    if s == t:
        print(0)
    else:
        visited.add(s)
        print(bfs([s, '']))