BOJ_14395 [ 4연산 ] [ 파이썬 ]

문제

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

14395번: 4연산

문제 해결 방법

BFS 로 문제를 해결하면 된다.

10억이 되기 때문에 set을 활용해서 방문 여부를 판단해야 된다.

그리고 연산자마다 우선 순위가 있기 때문에 우선 순위 높은 연산자부터 계산해서 queue에 넣었다.

다음 값이 t보다 크다면 굳이 이동할 필요가 없다. 그 이유는 되돌아 가는 방법이 -, / 두개 연산자 뿐인데

-를 하게 되면 값이 0이 되서 더이상 진행할 수가 없고, /하게되면 1이 되기 때문에 최소 연산에서 들어 갈 수 없기 때문이다. 그리고 t 값에 도달 했다면 bfs특성상 최소 연산으로 도착한 것이기 때문에 출력해주고 종료시켜주면 된다.

 

 

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_14395.py

jokerKwu/BOJ_Algorithm

import sys
from collections import deque

input = sys.stdin.readline
s, t = map(int, input().split())
queue = deque()
check = set()
queue.append((s,''))
check.add(s)
MAX = 10e9

if s == t:
    print(0)
else:
    res = -1
    while queue:
        c_v, c_s = queue.popleft()
        if c_v == t:
            res = c_s
            print(res)
            exit(0)

        n_v = c_v * c_v
        if 0 <= n_v <= MAX and n_v not in check:
            queue.append((n_v, c_s+'*'))
            check.add(n_v)

        n_v = c_v + c_v
        if 0 <= n_v <= MAX and n_v not in check:
            queue.append((n_v, c_s+'+'))
            check.add(n_v)

        n_v = 1
        if n_v not in check:
            queue.append((n_v, c_s+'/'))
            check.add(n_v)
    print(res)