[알고리즘] 숨바꼭질 2

구현 방식

• 기본적인 BFS 문제는 상하 좌우로 2차원 배열을 탐색 했다면,
• 해당 문제는 1차원 배열로, + 1 , - 1 , *2 로 탐색한다.
• 배열로 이쁘게 담아서 for문으로 만들자.
• 숨바꼭질 1 과는 다르게 이 문제는 모든 경우의 수를 탐색해야한다.
• 그러므로, visited 를 통해서 방문 했으면 스킵! 했던것을 이제 삭제하고 해당 이동 수로 몇번 방문 했는지를 세준다.

코드

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

const int MAXSIZE = 100001;
int graph[MAXSIZE] = {}; // 이동 횟수, INT_MAX 로 초기화
int visited[MAXSIZE] = {}; // 방문 횟수

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

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

		int nextPoses[] = { curr - 1 , curr + 1, curr * 2 };
		for (auto next : nextPoses)
		{
			if (canVisited(next))
			{
				// 다른 방식으로 동일 이동 횟수만큼 현재 위치로 도착한 경우
				if (graph[next] == graph[curr] + 1)
				{
					visited[next]++;
					q.push(next);
					graph[next] = graph[curr] + 1;
				}
				// 이동 횟수가 이 전 탐색 보다 적은 경우 또는 처음 방문 하는 경우
				else if (graph[next] > graph[curr] + 1)
				{
					visited[next] = 1;
					q.push(next);
					graph[next] = graph[curr] + 1;
				}
			}
		}

	}
}

bool canVisited(int pos)
{
	if (pos < 0)
		return false;
	if (MAXSIZE <= pos)
		return false;
	return true;
}