[C++] 백준 12852 1로 만들기 2

 
#include <iostream>
#include <queue>
 
int arr[1000001] = {};
 
int main()
{
	int N = 0;
	std::cin >> N;
 
	std::queue<std::pair<int,int>> que = {};
	que.push({ N, N });
 
	while (!que.empty())
	{
		int now = que.front().first;
		int prev = que.front().second;
		que.pop();
 
		if (now == 1)
		{
			arr[now] = prev;
			break;
		}
 
		if (arr[now])
		{
			continue;
		}
 
		else
		{
			arr[now] = prev;
		}
 
		if (now % 3 == 0)
		{
			que.push({ now / 3, now});
		}
 
		if (now % 2 == 0)
		{
			que.push({ now / 2, now });
		}
 
		que.push({ now - 1, now });
	}
 
	std::vector<int> ans = {};
 
	int check = 1;
	while (check != N)
	{
		ans.push_back(check);
		check = arr[check];
	}
 
	ans.push_back(N);
 
	std::cout << ans.size() - 1 << "\n";
 
	for (int i = ans.size() - 1; i >= 0; --i)
	{
		std::cout << ans[i] << " ";
	}
 
	return 0;
}

 

큐로 탐색했습니다.

들어올 경우 이전에 어떤 것인지 체크해줍니다.

나뉘면 넣어주고 안나뉘면 넘어갑니다. (1이 나올 때까지 반복합니다.)

1에서 N까지 어떻게 나와있는지 벡터에 넣어줍니다.