[C++] 백준 1697번 - 숨바꼭질

 

으... 너무 졸리다...

 

문제 1697번

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, k;
bool visited[100001];

void bfs(int n) {
	queue<pair<int, int>> q;
	q.push({ n,0 });
	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
        	q.pop();
		if (x == k) {
			cout << cnt << endl;
			break;
		}
		if (0 <= x - 1 && x - 1 <= 100000) {
			if (!visited[x - 1]) {
				visited[x - 1] = true;
				q.push({ x - 1,cnt + 1 });
			}
		}
		if (0 <= x + 1 && x + 1 <= 100000) {
			if (!visited[x + 1]) {
				visited[x + 1] = true;
				q.push({ x + 1,cnt + 1 });
			}
		}
		if (0 <= x * 2 && x * 2 <= 100000) {
			if (!visited[x * 2]) {
				visited[x * 2] = true;
				q.push({ x * 2,cnt + 1 });
			}
		}
	}
}

int main(void) {
	cin >> n >> k;
	visited[n] = true;
	bfs(n);
}