[BOJ]1697-숨바꼭질

1697

완전탐색인가 했는데 종료조건을 찾기가 힘들었다. bfs로 탐색하면 최소조건을 가장 먼저 찾으니 이 방법을 사용!

성공코드

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

int N, M;
int arr[100001];

queue<pair<int, int>> q;

void search()
{
	int cur = 0;
	int depth = 0;

	do
	{
		cur = q.front().first;
		depth = q.front().second;
		q.pop();

		if (cur + 1 <= 100000)
		{
			if (arr[cur + 1] == 0 || arr[cur + 1] > depth + 1)
			{
				q.push(make_pair(cur + 1, depth + 1));
				arr[cur + 1] = depth + 1;
			}
		}
		
		if (cur - 1 >= 0)
		{
			if (arr[cur - 1] == 0 || arr[cur - 1] > depth + 1)
			{
				q.push(make_pair(cur - 1, depth + 1));
				arr[cur - 1] = depth + 1;
			}
		}

		if (cur * 2 <= 100000)
		{
			if (arr[cur * 2] == 0 || arr[cur * 2] > depth + 1)
			{
				q.push(make_pair(cur * 2, depth + 1));
				arr[cur * 2] = depth + 1;
			}
		}

	} while (cur != M);
}

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	arr[N] = -1;

	q.push(make_pair(N, 0));

	if (N == M)
	{
		cout << 0;
	}
	else
	{
		search();

		cout << arr[M];
	}
}