[백준] 14395번 4연산 - Python / 알고리즘 중급 1/3 - BFS (연습)

---

---

---

💡 문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10$^9$)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

---

💭 접근

이 문제의 경우 단순한 BFS 문제처럼 방문 처리를 하는 visited를 입력 t의 크기를 같도록 풀면 입력의 최대가 10$^9$이므로 메모리 초과가 발생한다.

따라서 visited를 리스트가 아닌 set으로 선언한 뒤, 방문한 숫자를 set에 add하고 이미 존재한다면 건너뛰는 방식으로 문제를 해결해야한다.

---

📒 코드

from collections import deque

def bfs(s):
    q = deque()
    q.append((s, ''))
    visited.add(s)

    while q:
        s, opers = q.popleft()

        if s == t:
            return opers

        for oper in ['*', '+', '-', '/']:
            if oper == '*':
                ns = s * s
                if ns <= t and ns not in visited:
                    visited.add(ns)
                    q.append((ns, opers + oper))
            elif oper == '+':
                ns = s + s
                if ns <= t and ns not in visited:
                    visited.add(ns)
                    q.append((ns, opers + oper))
            elif oper == '-':
                ns = s - s
                if ns not in visited:
                    visited.add(ns)
                    q.append((ns, opers + oper))
            elif oper == '/' and s != 0:
                ns = int(s / s)
                if ns not in visited:
                    visited.add(ns)
                    q.append((ns, opers + oper))
    return -1

s, t = map(int, input().split())
visited = set()

if s == t:
    print(0)
else:
    print(bfs(s))

---

💭 후기

방문처리를 꼭 리스트가 아닌 다른 방법으로도 할 수 있다는 것을 배울 수 있었다.

---

🔗 문제 출처

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

---