백준 12852번 1로 만들기 2 C++

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

 

bfs탐색으로 풀 수 있는 문제인데 숫자 n이 1이 되기까지의 숫자들의 정보를 저장해야 하는 문제이다.

우선 최솟값은 bfs탐색을 하면서 쉽게 구할 수 있고, 

자신의 이전 값을 저장하는 parent 배열을 만들었다.

bfs탐색을 진행하면서 자신의 이전 값을 parent 배열에 저장하고, 숫자가 1이 되면 1부터 parent 배열을 통해 값이 n이 될 때까지 역추적? 하면서 값을 하나씩 저장한다.

저장된 정보를 역순으로 출력하면 n에서 1이 되는 과정의 숫자들이 출력된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

bool visited[1000001] = { false };
int parent[1000001] = { 0 };

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

	int n;
	cin >> n;
	queue<pair<int, int>> q;
	vector<int> ans;
	q.push({ n,0 });
	visited[n] = true;
	parent[n] = n;
	int cnt = 0;
	while (!q.empty()) {
		auto a = q.front();
		if (a.first == 1) {
			cnt = a.second;
			break;
		}
		q.pop();
		if (a.first % 3 == 0 && !visited[a.first / 3]) {
			q.push({ a.first / 3,a.second + 1 });
			visited[a.first / 3] = true;
			parent[a.first / 3] = a.first;
		}
		if (a.first % 2 == 0 && !visited[a.first / 2]) {
			q.push({ a.first / 2,a.second + 1 });
			visited[a.first / 2] = true;
			parent[a.first / 2] = a.first;
		}
		if (a.first - 1 > 0 && !visited[a.first - 1]) {
			q.push({ a.first - 1,a.second + 1 });
			visited[a.first - 1] = true;
			parent[a.first - 1] = a.first;
		}
	}
	cout << cnt << "\n";

	int i = 1;
	while (i != n) {
		ans.push_back(i);
		i = parent[i];
	}
	ans.push_back(n);
	reverse(ans.begin(), ans.end());
	for (auto a : ans) {
		cout << a << " ";
	}
};