[백준문제풀이] 1697 숨바꼭질

 

풀이일시 : 2020-11-02

​

 

문제 :

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

​

​

입력 :

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

ex)

5 17

​

​

출력 :

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

ex)

4

​

​

풀이 :

완전탐색을 통해 모든 경우의 수를 따져준다. 가장 빠른시간을 출력한다.

 

#include <iostream>
#include <queue>

using namespace std;
	
//visited 에 갈수있는 경우를 모두 탐색해준다 bfs를
int N, K, visited[100001] = { 0, };
queue<int> q;

//기본원리 : 각 visited에 방문횟수를 입력함으로써 숫자 x가 도달하려면
//몇번 가야되는지를 visited에 다 저장해두는것
int bfs() {
	q.push(N);
	visited[N] = 1;
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		//위치에 도달했다면 출력
		if (p == K) 
			return visited[p] - 1;
		//수빈이 현재위치-1 한 값이 0이상이고 방문한 적이없을경우
		//현재 값에서 레벨을(위치를) 1 증가시켜 큐에 넣어준다.
		if (p - 1 >= 0 && visited[p - 1] == 0) {
			visited[p - 1] = visited[p] + 1; //현재 p가 1이라면 이 자리엔 2를 넣어주는것 
			q.push(p - 1); //p-1값을 push 해준다
		}
		//수빈이 현재 위치의 +1이 100000보다 작거나 같고 방문한 적이 없을경우
		if (p + 1 <= 100000 && visited[p + 1] == 0) {
			visited[p + 1] = visited[p] + 1;
			q.push(p + 1);
		}
		//수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한적이 없을경우
		if (2 * p <= 100000 && visited[2 * p] == 0) {
			visited[2 * p] = visited[p] + 1;
			q.push(2 * p);
		}
	}
}
int main() {
	cin >> N >> K;
	printf("%d", bfs());
}