[BOJ] 숨바꼭질2

[BOJ] 숨바꼭질2

Problem URL : 숨바꼭질2

#include <queue>
#include <cstring>
#include <iostream>

using namespace std;
bool visited[100001];
int n, k;
queue<pair<int, int>> q;

int main() {
	scanf("%d %d", &n, &k);
	
	int ansTime = 2e9;
	int ansNum = 0;

	q.push({ n,0 });

	while (!q.empty()) {
		int location = q.front().first;
		int time = q.front().second;
		
		q.pop();
		if (time > ansTime) {
			break;
		}
		
		if (location == k) {
			if (ansTime == 2e9) {
				ansNum = 1; // 처음 k위치에 왔을 때 방법의 수는 1
                ansTime = time;
			} else {
				ansNum++; // 이후에는 방법의 수를 증가시켜준다.
            }
			continue;
		}

		visited[location] = 1;

		if (location + 1 <= 100000 && !visited[location + 1]) {
			q.push({ location + 1, time + 1 });
		}
		if (location - 1 >= 0 && !visited[location - 1]) {
			q.push({ location - 1, time + 1 });
		}
		if (location * 2 <= 100000 && !visited[location * 2]) {
			q.push({ location * 2, time + 1 });
		}

	}

	printf("%d\n%d", ansTime, ansNum);
	return 0;
}