백준_14395_4연산

🙋‍♀️ 문제

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

14395번: 4연산

 

🧩 알고리즘

최소 횟수를 구하는 문제이므로 BFS 알고리즘

정점: 정수

간선: 정수 → 정수

 

💡 아이디어

이 문제는 BFS로 최소 횟수가 되는 경로를 구해야 한다.

따라서, 큐에 정점만 넣는 것이 아니라, string형으로 경로까지 넣는다.

정점 방문 여부를 체크하기 위해서 set을 사용했다.

 

👩‍💻 코드

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
#include <set>

using namespace std;

const long long limit = 1000000000LL;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// input
	long long s, t;
	cin >> s >> t;
	
	// BFS
	set<long long> visited; // 방문 여부 체크
	queue<pair<long long, string>> q;
	q.push(make_pair(s, ""));
	visited.insert(s);
	
	while (!q.empty()) {
		long long cur;
		string str; // 경로
		tie(cur, str) = q.front();
		q.pop();

		if (cur == t) { // t로 바꿨으면 출력
			if (str.length() == 0) { // s와 t가 같은 경우
				str = "0";
			}
			cout << str << '\n';
			return 0;
		}
		// *, +, -, / 순으로 연산
		if (0 <= cur * cur && cur * cur <= limit && visited.count(cur * cur) == 0) {
			q.push(make_pair(cur * cur, str + "*"));
			visited.insert(cur * cur);
		}
		if (0 <= cur + cur && cur + cur <= limit && visited.count(cur + cur) == 0) {
			q.push(make_pair(cur + cur, str + "+"));
			visited.insert(cur + cur);
		}
		if (0 <= cur - cur && cur - cur <= limit && visited.count(cur - cur) == 0) {
			q.push(make_pair(cur - cur, str + "-"));
			visited.insert(cur - cur);
		}
		if (cur != 0 && 0 <= cur / cur && cur / cur <= limit && visited.count(cur / cur) == 0) { // 0 조건 처리
			q.push(make_pair(cur / cur, str + "/"));
			visited.insert(cur / cur);
		}
	}
	cout << -1 << '\n'; // t로 바꿀 수 없는 경우
	return 0;
}