[BOJ] 13549 숨바꼭질 3

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

13549번: 숨바꼭질 3

알고리즘: BFS

 

시간복잡도: O(V+E)

---

BOJ 1697 숨바꼭질의 다른 버전이다.

https://moon323.tistory.com/16

 

X*2 연산은 1초가 아닌 0초가 걸린다.

 

-> 그냥 X*2 연산은 시간을 증가시키지 않으면 된다.

 

#include <iostream>
#include <deque>
using namespace std;
int N, K, h, c[100001];
deque <int> Q;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	for (int i = 0; i <= 100000; i++)
		c[i] = 0x7fffffff;
	
	Q.push_back(N);
	c[N] = 0;
	
	while(!Q.empty())
	{
		h = Q.front();
		Q.pop_front();
        if (h == K) break;
		if (h != 0)
		{
			for (int x = h*2; x <= 100000; x*=2)
			{
				if (c[x] > c[h])
				{
					c[x] = c[h];
					Q.push_front(x);
				}
			}
		}
		
		for (int x : {h-1, h+1})
		{
			if (x < 0 || x > 100000) continue;
			if (c[x] > c[h]+1)
			{
				c[x] = c[h]+1;
				Q.push_back(x);
			}
		}
	}
	cout << c[K];
	return 0;
}