백준 25418 - 정수 a를 k로 만들기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/25418

25418번: 정수 a를 k로 만들기

A값을 K로 변환할 때 최소 연산 횟수를 구하는 문제입니다.

변환하는 방법은 +1을 하거나 *2을 할 수 있습니다.

최소 연산 횟수를 구하는 것이기에 BFS를 사용해야 하며, 다른 좌표로 이동하면서 K값으로 도착하면 이동횟수를 출력해주면 됩니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int check[1000001];

int bfs(){
	queue<pair<int, int>> q;
	q.push({N, 0});
	check[N] = 1;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == M) return y;
		int X_1 = x + 1;
		int X_2 = x * 2;
		if(X_1<= 1000000 && check[X_1] == 0){
			check[X_1] = 1;
			q.push({X_1, y+1});
		}
		if(X_2 <= 1000000 && check[X_2] == 0){
			check[X_2] = 1;
			q.push({X_2, y+1});
		}
	}
}

void solve(){
	cout << bfs();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	solve();	
	return 0;
}

질문 및 조언은 댓글을 남겨주세요