[BFS] BOJ 13549번 숨바꼭질 3

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

13549번: 숨바꼭질 3

- 문제파악

수빈이와 동생의 위치가 정수로 주어진다. 수빈이 위치에서 동생 위치로 가기위한 최소 시간을 출력하라

 

- 정답

 

주의해야하는 점

문제의 조건중에 순간이동은 0초가 걸린다.

그래서 순간이동을 했을 때 최소 시간이 0초가 될 수 있다.

예를 들어 동생이 2의 배수에 위치한다면 수빈이는 0초만에 이동 가능하다. (부럽다.)

 

#include "bits/stdc++.h"

using namespace std;

int arr[100002];

queue<int> q;

void func(int x, int k)
{
	int nCmp = arr[x];
	if (arr[x] == -1)
	{
		arr[x] = arr[k] + 1;
		q.push(x);
	}
	else
	{
		arr[x] = min(arr[x], arr[k] + 1);

		if(nCmp != arr[x])
			q.push(x);
	}
}

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

	fill(arr, arr + 100002, -1);

	int n,m;
	cin >> n >> m;

	if (n == m)
	{
		cout << 0 << "\n";
		return 0;
	}

	arr[n] = 0;
	q.push(n);

	while (!q.empty())
	{
		int k = q.front();
		q.pop();

		if (k == m)
			break;

		int x1 = k - 1,
			x2 = k + 1,
			x3 = k * 2;

		if (x1 >= 0)
			func(x1, k);

		if(x2 <= 100000)
			func(x2, k);

		if (x3 <= 100000)
		{
			int nCmp = arr[x3];
			if (arr[x3] <= 0)
			{
				arr[x3] = arr[k];
				q.push(x3);
			}
			else
			{
				arr[x3] = min(arr[x3], arr[k]);

				if (nCmp != arr[x3])
					q.push(x3);
			}

			
		}


	}

	cout << arr[m];

}