[백준][bfs] 12851 숨바꼭질2 c++구현

목차

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

문제

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
int visit[100001] = { 0 };  //시간 카운트

int N, K;
int cnt[100001] = { 0 };  //방법 수 카운트
int methods = 0;
int sec = 0;
vector<int> track;

void bfs() {
	queue<int> q;
	q.push(N);
	visit[N] = 1;
	cnt[N] = 1;
	while (!q.empty()) {
		int t = q.front();
		q.pop();

		if (t == K)
		{
			return;
		}
		for (int next : {t * 2, t - 1, t + 1}) {
			//범위 초과나는지 여부 확인
			if (next < 0 || next > 100000)
				continue;
			if (!visit[next]) {
				q.push(next);
				visit[next] += visit[t] + 1;
                //경우의 수는 각각의 수를 더한 것이다.
				cnt[next] += cnt[t];
			}
            // 시각이 같을 경우를 고려해주어야 한다
			else if (visit[next] == visit[t] + 1)
				cnt[next] += cnt[t];
		}

	}
}


int main() {

	cin >> N >> K;
	bfs();
	cout << visit[K]-1 << "\n";
	cout << cnt[K];

}
/*
5 100000
*/