백준 12851 // bfs암기, 정답 경우의수 구하기는 cnt[next]+=cnt[here]

12851번: 숨바꼭질 2 (acmicpc.net)

12851번: 숨바꼭질 2

* 정답 경우의수 구하기 핵심코드

for (int next : {now - 1, now + 1, now * 2}) {
			//1. 범위체크
			if (next >= 0 && next <= 100000)
			{
				//최초방문인경우
				if (!visited[next]) {
					visited[next] = visited[now] + 1;
					cnt[next] += cnt[now];
					q.push(next);
				}
				//두번째이상방문 and 최단거리방문인경우
				else if (visited[next] == visited[now] + 1) {
					cnt[next] += cnt[now];
				}
			}
			
		}

1. 경우의수는 덧셈으로 구현하라.

2. 맨 아래의 경우는 반영안되도록 최단거리체크 추가.

#include <bits/stdc++.h> 
#define prev aaa
#define next aaaa
using namespace std;
int ret1,ret2;
int n, k,dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[100004], cnt[100004];
vector<pair<int, int>> v;

#define MAX 100000

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < n;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n>>k ;
	
	/*
	* bfs algorithm
	* 1.초기화 	cnt[n] = 1;
	* 2.종료조건
	* 3.next 범위체크
	* 4.next 방문체크
	* 5.visit[next] 갱신
	* 5.1 q.push!!
	* 6.추가논리(cnt[next]+=cnt[now])
	*/
	queue<int> q;
	q.push(n);
	visited[n] = 1;
	cnt[n] = 1;
	bool flag = 0;
	while (q.size())
	{
		int now = q.front(); q.pop();
		for (int next : {now - 1, now + 1, now * 2}) {
			//1. 범위체크
			if (next >= 0 && next <= 100000)
			{
				//최초방문인경우
				if (!visited[next]) {
					visited[next] = visited[now] + 1;
					cnt[next] += cnt[now];
					q.push(next);
				}
				//두번째이상방문 and 최단거리방문인경우
				else if (visited[next] == visited[now] + 1) {
					cnt[next] += cnt[now];
				}
			}
			
		}
	}

	cout << visited[k] - 1 << "\n" << cnt[k];

}
/*
5 17
 */