[2] 숫자 변환하기 (BFS, 하향식 계산)

문제 설명
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y
입출력 예
x y n result
10 40 5 2
10 40 30 1
2 5 4 -1

입출력 예 설명
입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

---

문제 풀이

너비탐색이다.

처음에는 visited를 빼먹어서 시간초과가 낫다.

이후 추가하니 통과, 근데 하향식으로 푸는게 훨씬 빠르다는 걸 알았다.

#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int solution(int x, int y, int n) {
	int answer = -1;

	// 너비 탐색
	// 중복 되는 값은 visited 처리 해주기
	map<int, bool> visited;
	queue<pair<int, int>> q;
	q.push(make_pair(x, 0));
	while (q.empty() == false)
	{
		auto val = q.front();
		q.pop();
		if (visited[val.first])
			continue;

		if (val.first == y)
			return val.second;

		visited[val.first] = true;
		if (visited[val.first * 3] == false && val.first * 3 <= y)
			q.push(make_pair(val.first * 3, val.second + 1));
		if (visited[val.first * 2] == false && val.first * 2 <= y)
			q.push(make_pair(val.first * 2, val.second + 1));
		if (visited[val.first + n] == false && val.first + n <= y)
			q.push(make_pair(val.first + n, val.second + 1));
	}

	return answer;
}

 

개선 사항

근데 이렇기 하는 것 보다 하향식으로 y에서 x 로 내려가면서 찾는 것이 훨씬 빠르다.

그 이유는, y가 가진 숫자의 속성 (3으로 나눠지는지, 2로 나눠지는지)를 활용하기 때문에 큐에 들어가는 숫자의 개수가 현저히 줄어들기 때문이다.

개선된 코드:

#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int solution(int x, int y, int n) {
	int answer = -1;

	// 너비 탐색
	// 중복 되는 값은 visited 처리 해주기
	map<int, bool> visited;
	queue<pair<int, int>> q;
	q.push(make_pair(y, 0));
	while (q.empty() == false)
	{
		auto val = q.front();
		int num = val.first;
		int cnt = val.second;
		q.pop();
		if (visited[num])
			continue;

		if (num == x)
			return cnt;

		visited[num] = true;
		if (num % 3 == 0 && visited[num / 3] == false)
			q.push(make_pair(num / 3, cnt + 1));
		if (num % 2 == 0 && visited[num / 2] == false)
			q.push(make_pair(num / 2, cnt + 1));
		if (num - n >= x && visited[num - n] == false)
			q.push(make_pair(num - n, cnt + 1));
	}

	return answer;
}