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

BFS로 문제를 풀었습니다.

수빈이는 1초에 3가지 행동중 하나를 할 수 있습니다. (X는 현재위치)
1. X = X + 1;
2. X = X - 1;
3. X = X * 2;

이 3가지에 대해서 BFS를 통해서 탐색해나갔고
이미 방문한 곳은 visit배열에 몇초가 걸렸는지를 넣어둠으로서
위치에 대한 방문여부와, 시간을 저장할 수 있었습니다.

동생이 있는 위치를 찾으면 visit[동생위치]를 출력하였으며,
x*2를 했을때 배열을 초과할 수 있기 때문에
동생 위치 * 2 까지만 접근 가능하게 했습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

int N, K;
int visit[200010];

void BFS()
{
	int l = N;
	queue<int> q;
	visit[l] = 0;
	q.push(l);

	while (!q.empty()) {
		l = q.front();
		q.pop();

		if (l == K) {
			cout << visit[K] << endl;
			return;
		}

		if (l + 1 <= K && visit[l + 1] == -1) {
			q.push(l + 1);
			visit[l + 1] = visit[l] + 1;
		}
		if (l - 1 >= 0 && visit[l - 1] == -1) {
			q.push(l - 1);
			visit[l - 1] = visit[l] + 1;
		}
		if (l * 2 <= K * 2 && visit[l * 2] == -1) {
			q.push(l * 2);
			visit[l * 2] = visit[l] + 1;
		}
	}
}

int main(int argc, char *argv[])
{
	memset(visit, -1, sizeof(visit));

	cin >> N;
	cin >> K;

	BFS();
	
	return 0;
}