[BOJ] 1697 숨바꼭질

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

1697번: 숨바꼭질

 

알고리즘: BFS

 

시간복잡도: O(V+E) -> E<=3*10^5 이므로 TLE는 생각안해도 된다.

 

---

접근:

1. N -> K까지 최단 거리로 위치 이동

2. 한정된 이동 경로 (X-1, X+1, X*2)

 

-> 이 두가지 조건을 통해 BFS를 사용하면 된다는 것을 알 수 있다.

    N~K까지 각 위치를 정점으로 보고 X-1, X+1, X*2 연산을 간선으로 생각하면 된다.

 

 

참고)

이동한 점이 10^5 보다 크면 고려할 필요가 없다.

이게 문제의 N, K 조건이 이동하는 도중의 좌표들에게도 적용해야하는지

정확히 명시되어 있지 않아서 헷갈렸었는데, 10^5를 넘는 좌표는 고려할 필요가 없다는게 증명이 가능했다...

 

$$X*2-a = (X-b)*2+c=K\ 에서,\ (X*2>10^5,\ (X-b)*2\le 10^5,\ K\le 10^5)$$

$$\ a=b+c를\ 만족하는\ 자연수\ a,b,c가\ 항상\ 존재한다.$$

 

$$a=b+c를\ 만족하지\ 않는\ a는\ 1뿐이다.$$

$$a=1이라\ 하자.\; 그러면\ 조건에\ 의하여\ X*2-1=10^5을\ 만족해야\ 한다.$$

$$10^5는\ 짝수이므로\ 등식을\ 만족하지\ 않는다.$$

$$따라서,\ 10^5를\ 넘어가는\ 좌표들은\ 고려할\ 필요가\ 없다.$$

 

 

이 코드는 작성 당시, 10^5를 넘어가는 좌표에 대해서도 고려했었다. (추후 심화 숨바꼭질 버전에서 수정)

/*
fail 1: 
N이 0일 때 고려x
*/
#include <iostream>
#include <queue>
using namespace std;
int N, K, c[100001*2], h;
queue <int> Q;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	Q.push(N);
	c[N] = 1;
	while (!Q.empty())
	{
		h = Q.front();
		if (h == K) break;
		if (h-1 >= 0 && !c[h-1])
		{
			c[h-1] = c[h]+1;
			Q.push(h-1);
		}
		if (h < K && !c[h+1])
		{
			c[h+1] = c[h]+1;
			Q.push(h+1);
		}
		if (h < K && !c[h*2])
		{
			c[h*2] = c[h]+1;
			Q.push(h*2);
		}
		Q.pop();
	}
	
	cout << c[K]-1;
	return 0;
}