백준 16953번 A → B

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/16953 

 

 

16953번: A → B

 

 

이번 문제는 너비 우선 탐색(BFS) 문제였습니다.

 

 

 

《문제 풀이》

 

1. A → B 로 바꾸는 과정에서 int 범위를 벗어날 수 있으므로 long long 자료형 사용 

2. { A, 0 } 을 큐에 삽입 (0은 연산횟수)

3. 현재값에 2를 곱한 값과 가장 오른쪽에 1을 더한 값을 큐에 삽입

4. 현재값이 B와 같다면 연산횟수 + 1 반환 

5. 현재값이 B보다 크다면, 더 연산해도 B가 나올 수 없으므로 continue

 

 

 

 

《C++ 코드》

 

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll; // int 범위를 벗어나므로  

ll transform(int from, int to) {
	queue<pair<ll, ll>> q;
	q.push({from, 0});
	
	while(!q.empty()) {
		ll curVal = q.front().first;
		ll cnt = q.front().second;
		q.pop();
		
		// 현재값이 B와 같으면 연산횟수 + 1 반환   
		if(curVal == to){
			return cnt + 1;
		}
		
		// 현재값이 B보다 크면 더이상 삽입하지 않음  
		if(curVal > to)
			continue;
		
		// 큐에 삽입할 때마다 연산횟수 + 1	
		q.push({curVal * 2, cnt + 1});
		q.push({curVal * 10 + 1, cnt + 1});
	}
	
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int A, B;
	cin>>A>>B;
	cout<<transform(A, B);
	
	return 0;
}

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면