백준 12851 숨바꼭질 2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

 숨바꼭질1과는 다르게 '가장 빠른 시간으로 찾는 방법이 몇 가지인지'도 출력해야 하기 때문에, 큐에 넣을 때 visited 체크를 하지 않고 pop할 때 방문처리한다. 수빈이와 동생의 처음 위치가 같을 경우 0 1 을 출력하고 끝낸다.

 이동 시간이 이미 최소 이동 시간보다 큰 경우는 큐에 넣지 않았다.

#include<iostream>
#include<queue>
using namespace std;

bool visited[200000];

int main() {
	int n, k, min{ 100000 }, count{ 0 };
	cin >> n >> k;
	if (n == k) {
		cout << 0 << "\n" << 1;
		return 0;
	}
	else if (n > k) {
		cout << n - k << "\n" << 1;
		return 0;
	}

	queue<pair<int, int>> q;
	q.push({ n, 0 });

	while (!q.empty()) {
		int cur = q.front().first;
		int times = q.front().second;
		q.pop();
		visited[cur] = true;
		if (cur + 1 == k || cur - 1 == k || cur * 2 == k) {
			if (times == min)  //최소 시간인 경우
				count++;
			else if (times < min) {  //최소 시간 갱신
				count = 1;
				min = times;
			}
			continue;
		}
		if (cur < k && visited[cur + 1] == false) {
			if (times < min)
				q.push({ cur + 1,times + 1 });
		}
		if (cur > 0 && visited[cur - 1] == false) {
			if (times < min)
				q.push({ cur - 1, times + 1 });
		}
		if (cur < k && visited[cur * 2] == false) {
			if (times < min)
				q.push({ cur * 2, times + 1 });
		}
	}
	cout << min + 1 << "\n" << count;
}