백준 14395. 4연산

4연산

BFS 문제

DFS로도 가능할것같은데..?

1. 간단 설명

---

s와 t가 주어졌을 때

사칙연산을 통해서 s를 t로 만들어야한다

그 과정에 사용한 사칙연산을 출력하는 문제

2. 예시

---

7 392

7+7 14*14 196+196 을 통해 +*+연산으로 만들 수 있음

주의사항

1. 사칙연산의 아스키 코드 순서는 ‘*’, ‘+’, ‘-‘, ‘/’
2. 같은 수가 주어지면 0을 출력
3. 만들 수 없다면 -1을 출력

3. 알고리즘

---

이 문제의 가장 중요한 포인트는

엄청나게 큰 수의 방문관리를 어떻게 할 것인가 인 것 같다

10^9의 수를 방문체크를 하려면 일반적인 배열론느 4GB필요함!

1. s, t입력 받기
2. bfs 시작
	2-1. bfs 초기화 
		- 큐 생성, 시작 노드 추가, 방문처리
	2-2. bfs 시작. 큐의 맨 앞에서 노드 꺼냄
	2-3. 꺼낸 숫자가 t라면 지금까지 연산을 출력 후 종료
	2-4. 곱셈 연산 체크 : 만든적 있는지 확인 후 없다면 큐에 넣음
	2-5. 덧셈 연산 체크
	2-6. 뺄셈 연산 체크
	2-7. 나눗셈 연산 체크 : 자기 자신으로 나누므로 무조건 1이 나온다
3. bfs를 끝냈는데도 답이 안나왔다면 불가능한 경우이므로 -1 출력

첫 도전은 dfs로 도전했으나, 깊이 우선 탐색 특성상

가지치기 조건이 명확하지 않으면 “++++…“와 같이 계속 탐색한다는 문제가 발생했다

필요 변수

• long long int s, t s와 t는 최대 10^9이므로 이들의 연산은 int형을 초과할 수 있음
• 방문처리를 위한 unordered_set 사용
  • 일반적인 문제에서는 int 배열을 사용했지만, 수가 크고, 범위가 넓으므로 unordered_set을 사용함

4. 소스코드

---

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

long long int s, t;
unordered_set<long long int> visited;

void bfs(long long int num, string ans) {
	queue< pair<long long int, string> > qu;
	qu.push({ s, "" });
	visited.insert(s);

	while (!qu.empty()) {
		long long int num = qu.front().first;
		string ans = qu.front().second;
		qu.pop();

		if (num == t) {
			cout << ans;
			return;
		}

		if (num * num <= t && visited.find(num * num) == visited.end()) {
			qu.push({ num * num, ans + "*" });
			visited.insert(num * num);
		}
		if (num + num <= t && visited.find(num + num) == visited.end()) {
			qu.push({ num + num, ans + "+" });
			visited.insert(num + num);
		}
		if(visited.find(num - num) == visited.end()) { // 자기 자신을 빼면 어짜피 0임
			qu.push({ 0, ans + "-" });
			visited.insert(num - num);
		}
		if (num != 0 && visited.find(1) == visited.end()) { // 마찬가지로 자기 자신으로 나누면 1이다
			qu.push({ 1, ans + "/" });
			visited.insert(1);
		}
		
	}

	cout << "-1";
	return;
}

int main() {
	cin >> s >> t;
	if (s == t) {
		cout << "0";
		return 0;
	}

	bfs(s, "");

	return 0;
}

int visited, bool visited는 많이 써봤는데

unordered_set을 이용한 방문처리는 처음 접해보았다

visited.find(num * num) == visited.end() 와 같이

일치 조건을 찾는 방법이 익숙하지 않아 많이 헤맸다

많이 다뤄봐야겠다