백준 - 12851 [C++]

 이 문제는 bfs 를 이용해서 푸는 문제이다. 처음에는 이 문제를 풀 때 보통 bfs 구현처럼 큐에 push 할 때 visited 를 수정했다. 그러나 이 문제는 그렇게 하면 굉장히 복잡해지고 정답을 맞추기 쉽지 않아진다. 이 문제는 visited 를 큐에서 pop 하자마자 체크하면 간단히 풀리는 문제였다. 또한 visited 를 int 로 하여 최단 거리를 계산하지만, 이 경우 여러 경로를 탐색해야 하므로 bool 로 선언해서 문제를 푸는게 훨씬 간단하다. 너무 정형화된 패턴으로 문제를 풀면 복잡해진다는 교훈을 얻었다.

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, k, answer = -1, cnt;
bool visited[100001];

bool inRange(int x)
{
	if (0 <= x && x <= 100000)
	{
		return true;
	}
	return false;
}
int bfs()
{
	queue<pair<int, int>> q;

	visited[n] = true;
	q.push({ n, 0 });

	while (!q.empty())
	{
		int x = q.front().first;
		int sec = q.front().second;
		int next;
		q.pop();

		visited[x] = true;

		if (x == k && answer != -1)	// later visit
		{
			if (sec == answer)
			{
				cnt++;
			}
		}

		if (x == k && answer == -1)	// first visit
		{
			answer = sec;
			cnt++;
		}

		next = x + 1;
		if (inRange(next) && !visited[next])
		{
			q.push({ next, sec + 1 });
		}

		next = x - 1;
		if (inRange(next) && !visited[next])
		{
			q.push({ next, sec + 1 });
		}

		if (x != 0)
		{
			next = x * 2;
			if (inRange(next) && !visited[next])
			{
				q.push({ next, sec + 1 });
			}
		}
	}

	return answer;
}

int main()
{
	cin >> n >> k;

	bfs();

	cout << answer << '\n';
	cout << cnt << '\n';

	return 0;
}