풀이

1. 처음에는 1,000,000,000 크기로 선언했더니 바로 메모리가 초과되서 다른 방식으로 visited 를 체크할 방법이 필요했고 찾아봤더니 set으로 사용한다고 해서 set으로 해봤다.

2. int 형식을 사용하면 계산중의 변수들이 21억을 넘어가는 경우가 생길 수 있으므로 long long 형태로 잡고 들어가야 한다.

3. 결과로 출력될 문자열은 string 으로 선언해서 +연산을 해주면서 기록했다.

코드

#include <bits/stdc++.h>
#define Max 1000000001
using namespace std;

struct node {
	long long cur;
	int cnt;
	string code;
};

queue<node> q;
set<int> visited;

int s, t;

int bfs()
{

	while (!q.empty())
	{
		long long cur = q.front().cur;
		int cnt = q.front().cnt;
		string code = q.front().code;

		visited.insert(cur);

		q.pop();

		if (cur == t)
		{
			cout << code;
			return 0;
		}

		if (cur * cur < Max && visited.find(cur*cur) == visited.end() )
			q.push(node{ cur * cur, cnt + 1, code + '*' });

		if (cur + cur < Max && visited.find(cur + cur) == visited.end())
			q.push(node{ cur + cur, cnt + 1, code + '+' });
 
		if (cur != 0 && visited.find(cur / cur) == visited.end())
			q.push(node{ cur / cur, cnt + 1, code + '/' });
	}
	return -1;
}

int main()
{
	cin >> s >> t;

	if (s == t)
	{
		cout << "0";
		return 0;
	}
	
	q.push(node{ s, 0, ""});

	int result = bfs();

	if (result == -1)
	{
		cout << "-1";
		return 0;
	}

	return 0;
}

후기

visited 배열을 사용할 때 1,000,000 크기의 배열을 선언하면 4mb의 메모리를 사용한다고 한다.

한동안 정보처리기사 필기 시험을 준비하느라 블로그를 못 썼는데 다시 마음을 다잡고 올리도록 해야겠다.