[BOJ] 1697. 숨바꼭질

풀이

#include <iostream>
#include <queue>

#define MAX 100000

using namespace std;

typedef struct point{
	int loc;
	int cnt;
} point;

int N, K, rst = 10000000;
int is_visit[100001];
queue<point> Q;

point make_point(int loc, int cnt);
void bfs();

int main(){
	cin >> N >> K	
	bfs();
	cout << rst << endl;
}

void bfs(){
	Q.push(make_point(N, 0));
	is_visit[N] = 1;

	while(!Q.empty()){
		point p = Q.front();
		Q.pop();
		if(p.loc == K){
			rst = p.cnt;
			return;
		}
		if(p.loc + 1 <= MAX && !is_visit[p.loc + 1]){
			Q.push(make_point(p.loc + 1, p.cnt + 1));
			is_visit[p.loc + 1] = 1;
		}
		if(p.loc * 2 <= MAX && !is_visit[p.loc * 2]){
			Q.push(make_point(p.loc * 2, p.cnt + 1));
			is_visit[p.loc * 2] = 1;
		}
		if(p.loc - 1 >= 0 && !is_visit[p.loc - 1]){
			Q.push(make_point(p.loc - 1, p.cnt + 1));
			is_visit[p.loc - 1] = 1;
		}
	}
}

point make_point(int loc, int cnt){
	point p;
	p.loc = loc; p.cnt = cnt;
	return p;
}