[C++]백준13549번 숨바꼭질3

오늘은 백준13549번 숨바꼭질3 문제를 풀어보도록 하자.

처음엔 그냥 큐를 써서 BFS를 돌렸지만 TLE가 나왔다. 그래서 deque로 짜게 되었는데 우선 가장 짧은 시간 으로 가야하기 때문에

우선 고려해주어야 할 것은 *2이다. 따라서 우선순위 큐로 풀거나 *2를 먼저 계산해주는 deque 컨테이너를 써서 접근해야한다.

문제는 다음과 같다.

                               [접근법]

  1. *2 일 땐 시간이 걸리지 않으므로 우선적으로 처리하기 위해 push_front를 해주고 나머지 +1과 -1은 후에 처리해주기 때문에
  push_back을 해준다.
  
  2. 그 후 도착 값과 같으면 answer = cnt를 해주고 bfs함수를 종료한다.

                                     [코드]
#include <iostream>
#include <deque>
using namespace std;
bool visit[200001];
struct pos {
	int x;
	int cnt;
};
deque<pos>dQ;
int N, K, answer = 987654321;

void bfs() {
	while (!dQ.empty()) {
		int size_of_dQ = dQ.size();

		for (int i = 0; i < size_of_dQ; i++) {
			int x = dQ.front().x;
			int cnt = dQ.front().cnt;

			dQ.pop_front();
			if (x == K) {
				if (answer > cnt) {
					answer = cnt;
					return;
				}
			}
			if (x == 0) {
				if (!visit[x + 1]) {
					visit[x + 1] = true;
					dQ.push_back({ x + 1, cnt + 1 });
				}
			}
			else {
				if (x * 2 <= 200000) {
					if (!visit[x * 2]) {
						visit[x * 2] = true;
						dQ.push_front({ x * 2, cnt });
					}
				}
				if (x + 1 <= 200000) {
					if (!visit[x + 1]) {
						visit[x + 1] = true;
						dQ.push_back({ x + 1, cnt + 1 });
					}
				}
				if (!visit[x - 1]) {
					visit[x - 1] = true;
					dQ.push_back({ x - 1, cnt + 1 });
				}
			}
		}
	}
}

int main() {
	cin >> N >> K;
	dQ.push_front({ N,0 });
	visit[N] = true;
	bfs();
	cout << answer;
}