Category
알고리즘  DFS/BFS

[14395] 4연산

by Hwang

문제

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

풀이

사전 순서대로 너비 우선 탐색 방식으로 연산을 하여 t를 만들어 주는 방식으로 풀었습니다.

bfs 방식이기 때문에 가장 먼저 t를 만든 방식이 최소 연산을 의미합니다. 따라서 탐색을 멈추고, 해당 순서를 출력합니다.

탐색을 진행할 때 중요한 점은 현재 연산의 결과가 t를 넘어섰을 때 ‘*’, ‘+’ 의 연산은 더 이상 해주지 말아야 합니다. 또한 방문 처리를 통해 이미 구한 숫자에서 탐색을 막아줍니다

import sys
from collections import deque

s, t = map(int, sys.stdin.readline().split())
operators = ['*', '+', '-', '/']
visited = dict()
queue = deque([(s, "")])
visited[s] = True
result = -1

while queue:
    num, current = queue.popleft()
    if num == t:
        result = current
        break
    for operator in operators:
        if operator == '/' and num == 0:
            continue
        if (operator == '*' or operator == '+') and num > t:
            continue
        next_num = eval(f'{num}{operator}{num}')
        if next_num in visited:
            continue
        if next_num < 0:
            continue
        visited[next_num] = True
        queue.append((next_num, current+operator))

print(result if result != '' else 0)


 Comment