백준 12851 - 숨바꼭질2

12851번: 숨바꼭질 2

#include <iostream>
#include <queue>
using namespace std;
int N, K;
int findCount = 0;
int minFindTime = 1000000000;
int flag[100001] = { 0 };
void FindTime(int index, int time) {
	queue<pair<int,int>> q;
	q.push(make_pair(index, time));

	while (q.size() > 0) {
		int pos = q.front().first;
		int num = q.front().second;
		q.pop();
		if (num > minFindTime) {
			continue;
		}
		if (pos == K) {
			if (minFindTime == num) {
				findCount++;
				continue;
			}

			if (minFindTime > num) {
				minFindTime = num;
				findCount = 1;
				continue;
			}
			continue;
		}
		if (flag[pos] >= num) {
			flag[pos] = num;
			if (pos * 2 < 100001 && flag[pos * 2] >= num) {
				q.push(make_pair(pos * 2, num + 1));
			}
			if (pos + 1 < 100001 && flag[pos + 1] >= num) {
				q.push(make_pair(pos + 1, num + 1));
			}
			if (0 <= pos - 1 && flag[pos - 1] >= num) {
				q.push(make_pair(pos - 1, num + 1));
			}
		}
	}
}
int main() {
	for (int i = 0; i < 100001; i++) {
		flag[i] = 1000000;
	}

	cin >> N >> K;
	FindTime(N, 0);
	cout << minFindTime << endl;
	cout << findCount << endl;
	return 0;
}

 

원래는 큐가 아니라 재귀함수 형식으로 했었는데 이렇게 하면 스택 오버플로우가 떠서 큐로 바꿨다.