백준 12852 1로 만들기 2 (c++) : 피너클

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

12852번: 1로 만들기 2

bfs문제다.

1로 만드는것 뿐만 아니라 1로 만드는 방법을 출력해야한다.

int n;
bool visited[1000001];
vector<int> v[1000001];

사용할 변수다. v[i]는 i로 가는 방법을 나타낸다.

cin >> n;

queue<int> q;
q.push(n);
memset(visited, false, sizeof(visited));
visited[n] = true;
v[n].push_back(n);

기본 준비를 한다. v[n]은 처음 시작이니 n을 넣어준다.

while (!q.empty()) {
	int now = q.front();
	q.pop();
	if (now == 1) break;

q가 차있는동안 반복된다.

now에 q.front()를 넣고 pop한다.

만약 now가 1이라면 바로 반복문을 나온다.

	if (now % 3 == 0 && !visited[now / 3]) {
		q.push(now / 3);
		visited[now / 3] = true;
		v[now / 3].clear();
		for (int i = 0; i < v[now].size(); i++) v[now / 3].push_back(v[now][i]);
		v[now / 3].push_back(now / 3);
	}

만약 now가 3의 배수고 아직 now/3을 방문하지 않았다면

q에 now/3을 넣고 now/3을 방문했다고 표시한뒤

v[now/3]을 비운다. 그후 n에서 now까지 오는 방법을 전부 v[now/3]에 넣은다음 마지막으로 now/3을 넣는다.

	if (now % 2 == 0 && !visited[now / 2]) {
		q.push(now / 2);
		visited[now / 2] = true;
		v[now / 2].clear();
		for (int i = 0; i < v[now].size(); i++) v[now / 2].push_back(v[now][i]);
		v[now / 2].push_back(now / 2);
	}
	if (!visited[now - 1]) {
		q.push(now - 1);
		visited[now - 1] = true;
		v[now - 1].clear();
		for (int i = 0; i < v[now].size(); i++) v[now - 1].push_back(v[now][i]);
		v[now - 1].push_back(now - 1);
	}
}

이를 2의 배수와 now-1에서도 똑같이 하면 된다.

cout << v[1].size() - 1 << endl;
for (int i = 0; i < v[1].size(); i++) cout << v[1][i] << ' ';

 

마지막으로 v[1]의 크기를 출력한뒤 v[1]안의 값들을 전부 출력하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int n;
bool visited[1000001];
vector<int> v[1000001];

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

	cin >> n;

	queue<int> q;
	q.push(n);
    memset(visited, false, sizeof(visited));
	visited[n] = true;
	v[n].push_back(n);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (now == 1) break;

		if (now % 3 == 0 && !visited[now / 3]) {
			q.push(now / 3);
			visited[now / 3] = true;
			v[now / 3].clear();
			for (int i = 0; i < v[now].size(); i++) v[now / 3].push_back(v[now][i]);
			v[now / 3].push_back(now / 3);
		}
		if (now % 2 == 0 && !visited[now / 2]) {
			q.push(now / 2);
			visited[now / 2] = true;
			v[now / 2].clear();
			for (int i = 0; i < v[now].size(); i++) v[now / 2].push_back(v[now][i]);
			v[now / 2].push_back(now / 2);
		}
		if (!visited[now - 1]) {
			q.push(now - 1);
			visited[now - 1] = true;
			v[now - 1].clear();
			for (int i = 0; i < v[now].size(); i++) v[now - 1].push_back(v[now][i]);
			v[now - 1].push_back(now - 1);
		}
	}
	cout << v[1].size() - 1 << endl;
	for (int i = 0; i < v[1].size(); i++) cout << v[1][i] << ' ';
}

전체코드다.