백준_숨바꼭질

[ 해결 방법 ]

단순 BFS 문제이다. 현재 수빈이의 위치에서 갈 수 있는 방향(X+1, X-1, 2*X)을 큐에 넣고 K가 나올 때까지 계속 반복하면 된다.

[ 코드 ]

#include <iostream>
#include <queue>
using namespace std;
struct pos
{
	int x, t;
};
int N, K, Max;
queue<pos> q;
bool visit[200001];
int dir[3] = { -1,1,1 };
int main()
{
	cin >> N >> K;
	if (N == K)
	{
		cout << "0" << endl;
		return 0;
	}
	else if (K > N)
		Max = 2 * K;
	else
		Max = N;
	q.push(pos{ N, 0 });
	visit[N] = true;
	pos cur, next;
	while (!q.empty())
	{
		cur = q.front();
		q.pop();
		dir[2] = cur.x;
		for (int i = 0; i < 3; i++)
		{
			next.x = cur.x + dir[i];
			next.t = cur.t + 1;
			if (next.x == K)
			{
				cout << next.t << endl;
				return 0;
			}
			if (next.x < 1 || next.x > Max)
				continue;
			if (visit[next.x] == false)
			{
				visit[next.x] = true;
				q.push(next);
			}
		}
	}
	return 0;
}