[백준/C++] 16953 A → B

유형	난이도	완료일	링크	특이사항
백트래킹	실버2	23.04.04	https://www.acmicpc.net/problem/16953

 

 

내 코드

#include <iostream>

using namespace std;

int a, b;
int MIN = 1000000000;

void DFS(long long int n, int depth)
{
	if(n == b && depth<MIN)
	{
		MIN = depth;
		return;
	}
	
	if(n > b)
		return;
	
	DFS(n*2, depth+1);
	DFS(n*10+1, depth+1);
}

int main(void)
{
	cin >> a>> b;
	
	DFS(a,1);
	
	if(MIN == 1000000000)
		MIN = -1;
	cout<< MIN;
}

a에 *2를 하거나 *10+1을 반복하여 b가 되는 최소의 경우를 찾는 문제. 선택지가 두 개 이므로 경우의 수를 나열해보면 트리 구조로 표현할 수 있다. 트리를 순회하는 DFS나 BFS로 모든 가능한 경우를 따져보고 최소 경우를 출력한다.

다른 풀이

#include <stdio.h>
#include <queue>
using namespace std;

int main(){
	int A,B;
	int ans = -1;
	queue<pair > q;
	
	scanf("%d %d",&A,&B);
	
	q.push(make_pair(A,1));
	
	while(!q.empty()){
		long long int k = q.front().first;
		int n = q.front().second;
		q.pop();
		
		if(k==B){
			ans = n;
			break;
		}
		
		if(k*2<=B)
			q.push(make_pair(k*2,n+1));
		if(k*10+1<=B)
			q.push(make_pair(k*10+1,n+1));
	}
	
	printf("%d",ans);
	
	return 0;
}
//https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-16953%EB%B2%88-A-%E2%86%92-B-CC

큐를 이용한 풀이다. 연산하는 값을 담는 int와 연산 횟수를 담는 int 두 가지를 가지는 pair를 큐에 담는다. 큐에 들어온 특정 값에 대해 B를 초과하지 않는다면 두 가지 연산을 모두 진행하여 큐에 담고 큐가 빌 때까지 반복문이 실행되기 때문에 결국 모든 경우를 다룰 수 있다. 그리고 연산 횟수가 적은 경우부터 순서대로 계산되기 때문에 정답을 찾는 순간 출력하면 그것이 최소 경우가 된다.

큐를 이용해서 모든 경우를 탐색하는 방법에 대해 생각해보지 못했다. 큐도 적극 활용해야겠다.