[ C++ ] #1697 숨바꼭질

 

이는 좀 특이하게 1차원 BFS문제이다.

2차원에서는 상하좌우로 BFS를 진행했다면 이 문제에서는 앞으로 뒤로 2배앞으로 이렇게 세개로 진행하면 된다.

이렇게 배열을 찾아가다가 동생 위치에 숫자가 써지면 답이 된다!

 

코드로 짜보자!

 

코드는 금방짰다!

1차원 배열에서 BFS는 처음이라 낯설었지만 이해하고 나니 코드가 어렵지는 않았다.

 

#include <iostream>
#include <Queue>

using namespace std;

int road[100001];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K;
	cin >> N >> K;

	road[N]  =1;

	queue<int> Q;
	Q.push(N);

	while (road[K] == 0) {

		int a= Q.front();
		Q.pop();

		//앞으로
		if (a + 1 > 100000){}
		else{
			if (road[a + 1] == 0 || road[a + 1] > road[a] + 1) {
				road[a + 1] = road[a] + 1;
				Q.push(a + 1);
			}
		}
	
		//뒤로
		if (a - 1 < 0) {}
		else {
			if (road[a - 1] == 0 || road[a - 1] > road[a] + 1) {
				road[a - 1] = road[a] + 1;
				Q.push(a - 1);
			}
		}

		//두배
		if (a *2 > 100000){}
		else {
			if (road[a * 2] == 0 || road[a * 2] > road[a] + 1) {
				road[a * 2] = road[a] + 1;
				Q.push(a * 2);
			}
		}
	}
	cout << road[K] - 1;
	return 0;
}