[백준 16953] A->B

문제설명

알고리즘

1. A,B를 입력 받는다

2. 함수로 이동하여 B로 부터 A로 만든다

3. queue에 B의 값을 넣고, 나누기 2 혹은 -1 한 뒤 , 10으로 나누었을 때 값이 A보다 작지 않으면 queue에 넣는다

4. a의 값이 현재 값과 같아지는 순간이 나오면 그 초를 결과로 출력한다

5. 만약 같아지는 순간이 오지 않았다면, -1을 출력한다

코드

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

int answer;
bool check = false;

void bfs(int x,int y) {
	
	queue <double> q; // 나눗셈 연산에 의해 비교할 때 소수점 까지 비교필요
	q.push(y);

	while (!q.empty()) {
		
		int size = q.size();//현재 queue에 담겨있는 원소의 수 구하기
		
		for (int i = 0; i < size; i++)
		{
			double current = q.front();
			q.pop();

			if (current == x)
			{
				check = true;
				return;
			}

			if (current/2 >=x ) { // 나누기 2를 했을때 아직 값에 도달하지 못했을 때
				q.push(current/2);
			}
			if ((current-1)/10 >=x) { //-1 하고 10으로 나누었을떄 
				q.push((current - 1) / 10);
			}
		}	answer++;// 필요한 연산의 수
		
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);

	int a, b;
	cin >> a >> b;

	bfs(a, b);
	if (check)
		cout << answer +1;
	else
		cout << -1;
}

고찰

이번 문제는 dfs 혹은 bfs를 사용하면 메모리 초과가 발생하는 문제였다

왜냐하면 숫자의 범위가 10^9였기 때문에 방문 표시를 10^9개 만큼 만들면 메모리 초과가 발생하기 때문이다

 

따라서 필요한 문제 해결 방법은 바로 거꾸로 연산하는 것이다

2에서 162로 갈생각을 하면 안되고 162에서 2로 가는 연산을 해야하는 것이다

 

전혀 생각하지 못했던 방법이어서 구글링 해서 이유를 겨우 찾았다

 

거꾸로 연산하다보니 나눗셈 연산을 사용했는데, 소수점까지 정확하게 비교하기 위해 int형이 아니라 double 자료형을 사용했다