[G4] 백준 14395번 4연산 C++ 너비 우선 탐색, 해시 셋

리뷰

 

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

4가지 연산을 통해 초기 숫자 s를 t로 만들 수 있는 방법을 찾는 문제

 

 

전역 변수

• s, t : 초기 정수와 목표 정수를 저장할 변수
• v : 방문 여부를 체크할 해시 셋

 

함수

1. bfs

string bfs() {
	queue<P> q;
	q.push({ s * s, "*" });
	v.insert(s * s);
	q.push({ s * 2, "+" });
	v.insert(s * 2);
	q.push({ 0, "-" });
	v.insert(0);
	q.push({ 1, "/" });
	v.insert(1);

	while (!q.empty()) {
		P p = q.front(); q.pop();
		ll c = p.v;
		string s = p.s;
		if (c == t) return s;

		ll nv = c * c;
		if (nv <= t && !v.count(nv)) {
			v.insert(nv);
			q.push({ nv, s + '*' });
		}

		nv = c + c;
		if (nv <= t && !v.count(nv)) {
			v.insert(nv);
			q.push({ nv, s + '+' });
		}
	}
	return "-1";
}

 

초기 정수에서 목표 정수까지 도달하기까지의 연산 과정을 출력하기 위한 함수

 

문제풀이

1. s, t에 값을 입력 받고, s와 t가 동일하다면 0을 출력하고 함수를 종료해준다.
2. bfs함수를 호출한다.
3. P타입의 큐 q를 초기화 하고, 각 초기 연산한 정수와 연산 결과를 사전순으로 q에 push해준다.
4. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어준다.
5. 변수 c와 s에 현재 요소의 정수와 누적 연산을 파싱하여 저장해 준다.
6. 기저 조건으로 만약 c와 t가 동일하다면 s를 리턴해 준다.
7. 변수 nv를 c * c로 저장하고 t이하이면서 방문하지 않았다면 방문처리 후 q에 push해준다.
8. 변수 nv에 c + c값을 저장하고 t이하이면서 방문하지 않았다면 방문처리 후 q에 push해준다.
9. while루프가 종료될때까지 기저조건에 도달하지 못하였다면 "-1"을 리턴해 준다.
10. bfs함수의 리턴값을 출력해 준다.

 

트러블 슈팅

1. s와 t의 범위가 1~1e9여서 int범위 내로 처리가 가능하다고 생각하였다.
2. s * s값이 최대 1e18이므로 long long타입의 값으로 변경하여 AC를 받았다.

 

참고 사항

• t보다 값이 커질 경우 정답이 될 수 없다.
• -, /연산의 값은 항상 0, 1이므로 초기에 연산값을 넣어주고 시작하는것이 좋다.
• 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

 

정답 코드

#include<iostream>
#include<queue>
#include<unordered_set>
#define ll long long
using namespace std;

ll s, t;
unordered_set<ll> v;

struct P {
	ll v;
	string s;
};

string bfs() {
	queue<P> q;
	q.push({ s * s, "*" });
	v.insert(s * s);
	q.push({ s * 2, "+" });
	v.insert(s * 2);
	q.push({ 0, "-" });
	v.insert(0);
	q.push({ 1, "/" });
	v.insert(1);

	while (!q.empty()) {
		P p = q.front(); q.pop();
		ll c = p.v;
		string s = p.s;
		if (c == t) return s;

		ll nv = c * c;
		if (nv <= t && !v.count(nv)) {
			v.insert(nv);
			q.push({ nv, s + '*' });
		}

		nv = c + c;
		if (nv <= t && !v.count(nv)) {
			v.insert(nv);
			q.push({ nv, s + '+' });
		}
	}
	return "-1";
}

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