[PS] 백준 1697 - 숨바꼭질

📌 알고리즘 분류

---

해당 문제는 BFS에 대한 이해가 필요한 문제입니다.
BFS

📖 문제

---

백준 1697

간단한 1차원 BFS 문제입니다.

💻 코드

---

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
bool visit[100001];
int graph[100001];
queue<int> q;
int n, k;

void BFS()
{
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (int i = 0; i < 3; i++)
		{
			int next_x;
			if (i == 0)
			{
				next_x = cur - 1;
			}
			else if (i == 1)
			{
				next_x = cur + 1;
			}
			else
			{
				next_x = 2 * cur;
			}

			if (0 <= next_x && next_x <= 100000)
			{
				if (visit[next_x]==false||graph[next_x] > graph[cur] + 1)
				{
					q.push(next_x);
					graph[next_x] = graph[cur] + 1;
					visit[next_x] = true;
				}
			}
		}
	}


}

int main()
{
	memset(graph, -1, sizeof(int) * 100001);
	memset(visit, false, sizeof(bool) * 100001);

	cin >> n >> k;
	graph[n] = 0; visit[n] = true;

	q.push(n);
	BFS();

	cout << graph[k] << "\n";
}