[BOJ] 백준 13549번: 숨바꼭질3 C++ : 아주정은

이건 문제가 엄청 어려운건 아닌것같은데, 생각을 많이 하지 않아서 좀 해맸다.

오지게 틀렸다....

​후기를 쓰자면, 처음에는 BFS로 큐를 사용해서 풀려고했다. 근데 가장 작은 시간을 출력해야하기 때문에 적절하지 않았다.

​그래서 우선순위 큐를 사용할려고하였다. 근데 우선순위큐를 사용할경우 반례들이 발생한다.

​흠....그래서 구글에 백준 13549번 c++ 이라는 키워드를 검색하고 여러가지 정답코드를 봤는데,

​데큐를 이용하는게 나쁜생각같지는 않아서 데큐로 골랐다. 실은 나는 평소 The Q를 좋아하기 때문에 선택한 경향도 없지않아 있다.

​음 일단, 곱하기 2를 할경우에는 앞으로 푸쉬하고, 더하기 빼기를 할때는 뒤로 푸시를 한다.

​생각해보자. 5에서 17을 찾아갈때, 타임이 0000011111 이런식으로 있을때, 앞에서만 pop을 하면 앞에는

타임이 가장 작은것들만 들어가고 자연스럽게 뒤로 타임이 높은게 들어간다.

​그래서 데큐를 사용하면 괜찮다.

​구현은 코드가 짧기때문에 설명은 생략한다.

#include <iostream>
#include<deque>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[100001];



int main()
{
	int a, b;
	cin >> a >> b;
	deque<Que> Q;
	Q.push_front({ a,0 });
	vis[a] = true;

	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop_front();

		if (cur.x == b) {
			cout << cur.time << endl;
			break;
		}

		if (cur.x * 2 < 100001 and vis[cur.x * 2] == false) {
			Q.push_front({ cur.x * 2,cur.time });
			vis[cur.x * 2] = true;
		}
		if (cur.x + 1 < 100001 and vis[cur.x + 1] == false) {
			Q.push_back({ cur.x + 1,cur.time + 1 });
			vis[cur.x + 1] = true;
		}
		if (cur.x - 1 >= 0 and vis[cur.x - 1] == false) {
			Q.push_back({ cur.x - 1,cur.time + 1 });
			vis[cur.x - 1] = true;
		}
	}

}