백준 1463번 : 1로 만들기 : bfs로 풀었다.

1463번: 1로 만들기

1463번: 1로 만들기

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

#include <iostream>
#include <queue>
using namespace std;

struct Node
{
	int num;
	int cnt;
};

queue <Node> que;

void bfs(int n, int lev)
{
	Node node, temp;
	node = { n, lev };
	que.push(node);
	while (1)
	{
		node = que.front();
		que.pop();
		if (node.num == 1)
			break;
		if (node.num % 3 == 0)
		{
			//temp = { node.num / 3, node.cnt + 1 };
			que.push({ node.num / 3, node.cnt + 1 });
		}
		if (node.num % 2 == 0)
		{
			que.push({ node.num / 2, node.cnt + 1 });
		}
		que.push({ node.num - 1, node.cnt + 1 });
	}
	cout << node.cnt;
}

int main(void)
{
	int n;
	cin >> n;
	bfs(n, 0);

}

예전에 배운 bfs로 풀어봤다. 

 

한번에 통과!!!