c++ 백준_12851_"숨바꼭질 2"

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

BFS를 활용하여 풀었다.

​

보통 BFS를 하면 방문 체크를 하는데

목적지에 도착한 경우의 수까지 해야하니

거리를 담은 배열을 하나둬

해당 좌표의 배열칸에 저장된 거리 이하인 것들만 queue에 담았다.

​

​

*

몇번 시도했을 때 자꾸 안되길래 보니

N == K 일 때,

이때까지 0, 0이 나왔었다.

​

시간은 0 초이더라도

경우의 수는 하나의 경우기 때문에

0, 1 이 나와야했다.

 

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

#define INF 1000000
#define MAX_SIZE 200001
int N, K;
int nOfCase;
int dist[MAX_SIZE];
int fast = 0;


void BFS() {

	int size = max(N, K);
	for (int i = 0; i <= size*2; i++) {
		dist[i] = INF;
	}
	
	dist[N] = 0;

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

	while (!q.empty()) {
		int now = q.front().first;
		int dst = q.front().second;
		q.pop();

		if (now == K) {
			fast = dst;
			nOfCase++;
			continue;
		}

		if(now + 1 < MAX_SIZE)
			if (dst + 1 <= dist[now + 1]) {
				dist[now + 1] = dst + 1;
				q.push({ now + 1,dst + 1 });
			}
		if (now - 1 >= 0)
			if (dst + 1 <= dist[now - 1]) {
				dist[now - 1] = dst + 1;
				q.push({ now - 1, dst + 1 });
			}

		if (now * 2 < MAX_SIZE)
			if (dst + 1 <= dist[now * 2]) {
				dist[now * 2 ] = dst + 1;
				q.push({ now * 2, dst + 1 });
			}
	}
}

int main(void) {

	cin >> N >> K;

	BFS();

	cout << fast << "\n";
	cout << nOfCase;
}