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

#include <iostream>
#include <queue>
#define MAX_LOCATION 100001
using namespace std;

int K, N;
int visited[MAX_LOCATION]{false};

void BFS(int curr);

int main()
{
	ios::sync_with_stdio(false);

	cin >> N >> K;

	BFS(N);
}

void BFS(int curr)
{
	queue<pair<int, int>> q;
	q.push({ curr, 0 });
	visited[curr] = true;

	while (!q.empty())
	{
		int currNode = q.front().first;
		int currSec = q.front().second;
		q.pop();

		if (currNode == K)
		{
			cout << currSec;
			break;
		}

		if (MAX_LOCATION > currNode - 1 && !visited[currNode - 1])
		{
			q.push({ currNode - 1, currSec + 1 });
			visited[currNode - 1] = true;
		}

		if (MAX_LOCATION > currNode + 1 && !visited[currNode + 1])
		{
			q.push({ currNode + 1, currSec + 1 });
			visited[currNode + 1] = true;
		}
			

		if (MAX_LOCATION > currNode * 2 && !visited[currNode * 2])
		{
			q.push({ currNode * 2, currSec + 1 });
			visited[currNode * 2] = true;
		}
	}
}

 

풀이

1. BFS를 사용하여 1초당의 X - 1, X + 1, X * 2 경우의 수를 구한다.
2. 방문한 곳을 표시하는 것이 메모리의 양을 초과하지않도록 계산한다.