백준 숨바꼭질 3 (복습)

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제는 어렵지 않습니다. 키포인트는 여기서 가장 짧은 시간을 찾는거여서 bfs를 사용해주고 찾는 순서가 순간이동-> 걷기 순으로 queue에 입력해줘야 빠른순서를 찾을수 있습니다.

struct Data {
	int pos;
	int sec;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//수빈 n, 동생 k
	int n, k;
	cin >> n >> k;
	//걷거나 순간이동 
	//1초후 걸으면 x-1 x+1
	//0초후 순간이동  2*x
	queue<Data>q;
	vector<bool>bCheck(100001,false);
	if (n == k) {
		cout << 0;
		return 0;
	}
	Data d;
	d.pos = n;
	d.sec = 0;
	q.push(d);
	bool bEnd = false;
	while (!q.empty()) {
		Data start = q.front();
		q.pop();
		if (bEnd == true) {
			break;
		}
		bCheck[start.pos] = true;
		for (int i = 0; i < 3; i++) {
			
			Data tmp;
			if (i == 2) {
				//걷기
				tmp.pos = start.pos +1;
			}
			else if (i==1) {
				//걷기
				tmp.pos = start.pos - 1;
			}
			else if (i == 0) {
				//순간이동
				tmp.pos = start.pos * 2;
			}

			if (tmp.pos < 0 || tmp.pos>100000) {
				continue;
			}
			if (bCheck[tmp.pos] == true) {
				continue;
			}

			if (i == 1 || i == 2) {

				tmp.sec = start.sec + 1;
			}
			else {

				tmp.sec = start.sec;
			}
			bCheck[tmp.pos] = true;
			if (k==tmp.pos) {
				 cout <<tmp.sec;
				 bEnd = true;
				 break;
			}
			q.push(tmp);
		}
	}
	return 0;
}