[백준 / BOJ] 1697번 : 숨바꼭질

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

1697번: 숨바꼭질

 

 

---

 

 

문제

---

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

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

 

입력

---

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

 

출력

---

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

 

예제 입력

---

5 17

예제 출력

---

4

 

코드 

---

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

int n, k, seconds;
bool visited[100001];
queue<int> q;

void bfs(int v) {
	visited[v] = true;
	q.push(v);

	while (!q.empty()) {
		int size = q.size();
		while (size--) {
			int x = q.front();
			if (x == k) return;
			q.pop();
			if (x - 1 >= 0 && x - 1 <= 100000 && !visited[x - 1]) {
				q.push(x - 1);
				visited[x - 1] = true;
			}
			if (x + 1 <= 100000 && !visited[x + 1]) {
				q.push(x + 1);
				visited[x + 1] = true;
			}
			if (2 * x <= 100000 && !visited[2 * x]) {
				q.push(2 * x);
				visited[2 * x] = true;
			}
		}
		seconds++;
	}
}

int main() {
	cin >> n >> k;

	bfs(n);

	cout << seconds;
	return 0;
}

 

 

 

---

 

 

bfs를 사용하여, 각각의 좌표에서 이동할 수 있는 모든 좌표를 향하여 탐색한다. 탐색을 할 때, level이 증가할 때마다 초를 세어 주기 위해 큐의 사이즈를 구하여 반복문을 돌렸다. 반복문을 돌며 계속 탐색을 진행하다가 x값과 k값이 같아지면 리턴하면 끝이다.