[알고리즘] 숨바꼭질

구현 방식

• 기본적인 BFS 문제는 상하 좌우로 2차원 배열을 탐색 했다면,
• 해당 문제는 1차원 배열로, + 1 , - 1 , *2 로 탐색한다.
• 배열로 이쁘게 담아서 for문으로 만들자.

코드

• 최종 코드는 아래와 같다.

const int MAXSIZE = 100001;
int graph[MAXSIZE] = {};
bool visited[MAXSIZE] = {};

void bfs(int N, int K)
{
	queue<int> q;
	q.push(N);
	visited[N] = true;

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

		int nextPoses[] = { curr - 1 , curr + 1, curr * 2 };
		for (auto next : nextPoses)
		{
			if (canVisited(next))
			{
				q.push(next);
				visited[next] = true;
				graph[next] = graph[curr] + 1;
				if (next == K) return;
			}
		}

	}
}

bool canVisited(int pos)
{
	if (pos < 0)
		return false;
	if (MAXSIZE <= pos)
		return false;
	return !visited[pos];
}