[BOJ]14395번: 4연산 (c++)

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

14395번: 4연산

 

 

방법 1: 큐에 {다음 숫자, 이제까지의 연산자 문자열} 저장하기

#include <iostream>
#include <queue>
#include <set>

using namespace std;

const long long limit = 1000000000LL;

long long calculate(long long n, char c)
{
	long long res = -1;

	if (c == '*')
	{
		res = n * n;
	}
	else if (c == '+')
	{
		res = n + n;
	}
	else if (c == '-')
	{
		res = n - n;
	}
	else if (n > 0 && c == '/')
	{
		res = n / n;
	}

	if (res > limit)
	{
		res = -1;
	}
	return res;
}

void bfs(long long s, long long t)
{
	queue<pair<long long, string>> q;
	set<long long> visit;
	q.push({ s, "" });
	visit.insert(s);

	// 사전순 출력을 위한 연산자 순서
	char ops[] = { '*', '+', '-', '/' };

	while (!q.empty())
	{
		long long n = q.front().first;
		string str = q.front().second;
		q.pop();

		if (n == t)
		{
			if (str.size() == 0)
			{
				cout << 0;
			}
			else
			{
				cout << str;
			}
			return;
		}

		for (int i = 0; i < 4; ++i)
		{
			// 연산 결과가 0 이상 10^9 이하이고, 전에 방문한적이 없다면
			long long next = calculate(n, ops[i]);
			if (next >= 0 && visit.count(next) == 0)
			{
				// set에 push해서 방문체크
				visit.insert(next);
				// 큐에 {다음숫자, 이제까지의 문자열 + 새 연산자} push 
				q.push({ next, str + ops[i] });
			}
		}
	}

	// s ~ t로 변환 불가능할 때 
	cout << -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long s, t;
	cin >> s >> t;

	bfs(s, t);

	return 0;
}

 

 

방법 2: 2개의 맵에 각각 이전 인덱스, 현재 연산자를 저장

#include <iostream>
#include <queue>
#include <map>

using namespace std;

const long long limit = 1000000000LL;
map<long long, long long> bf_idx;
map<long long, char> op;

long long calculate(long long n, char c)
{
	long long res = -1;

	if (c == '*')
	{
		res = n * n;
	}
	else if (c == '+')
	{
		res = n + n;
	}
	else if (c == '-')
	{
		res = n - n;
	}
	else if (n > 0 && c == '/')
	{
		res = n / n;
	}

	if (res > limit)
	{
		res = -1;
	}

	return res;
}

void print(int n)
{
	// 이전 인덱스가 -1 일때까지 print함수 재귀호출 & 출력
	if (bf_idx[n] == -1)
	{
		return;
	}

	print(bf_idx[n]);

	cout << op[n];
}

bool bfs(long long s, long long t)
{
	queue<long long> q;
	q.push(s);
	bf_idx[s] = -1;

	// 사전순 출력을 위한 연산자 순서
	char ops[] = { '*', '+', '-', '/' };

	while (!q.empty())
	{
		long long n = q.front();
		q.pop();

		if (n == t)
		{
			return true;
		}

		for (int i = 0; i < 4; ++i)
		{
			// 연산 결과가 0 이상 10^9 이하이고, 전에 방문한적이 없다면
			long long next = calculate(n, ops[i]);
			if (next >= 0 && bf_idx.find(next) == bf_idx.end())
			{
				// next의 이전 인덱스 : 현재숫자
				bf_idx[next] = n;
				// 현재 숫자 ~ next에 필요한 연산자
				op[next] = ops[i];
				q.push(next);
			}
		}
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long s, t;
	cin >> s >> t;

	// s와 t가 같을 때
	if (s == t)
	{
		cout << 0;
	}
	// s ~ t로 변환 가능할 때
	else if (bfs(s, t))
	{
		print(t);
	}
	// s ~ t로 변환 불가능할 때 
	else
	{
		cout << -1;
	}

	return 0;
}

 

 

TIP1

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

 

10^9는 int의 범위에 포함되지만, 중간에 연산되는 숫자가 int 범위를 넘어설 수 있으므로

long long형으로 수를 처리하는 것이 안전하다. 

 

 

TIP2

그러면 bfs를 위한 메모이제이션은??

 

10^9크기의 bool배열을 만드는 것은 생각만 해도 비효율적이다.

단순히 해당 숫자를 방문 했느냐, 안했느냐만 판단하면 되므로

구현 방법에 따라 map 또는 set 자료구조를 선택해서 포함여부를 판단하면 된다.