백준 1697번 C++

#include <iostream>

#include <queue>

#include <string>

#include <cstring>

using namespace std;

const int MAX = 100001;

int n, k;

queue<pair<int, int>> q;

int visited[MAX];

int bfs(int i) {

int answer = 0;

if (i == k)

return answer;

q.push(make_pair(i, 0));

visited[i] = 1;

while (!q.empty()) {

int currentlocation = q.front().first;

int currenttime = q.front().second;

q.pop();

if (currentlocation == k) {

answer = currenttime;

break;

}

if ((currentlocation - 1) >= 0 ) {

if (visited[currentlocation-1] == -1) {

q.push(make_pair(currentlocation - 1, currenttime + 1));

visited[currentlocation-1] = 1;

}

}

if ( (currentlocation + 1) < MAX) {

if (visited[currentlocation+1] == -1) {

q.push(make_pair(currentlocation + 1, currenttime + 1));

visited[currentlocation+1] = 1;

}

}

if ( (currentlocation *2) < MAX) {

if (visited[currentlocation*2] == -1) {

q.push(make_pair(currentlocation * 2, currenttime + 1));

visited[currentlocation*2] = 1;

}

}

}

return answer;

}

int main(void) {

cin >> n >> k;

memset(visited, -1, sizeof(visited));

cout << bfs(n);

return 0;

}