백준 1697 : 숨바꼭질

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

1. 접근

• X에 있을 때 수빈이는 순간이동을 하거나, +1이동, -1이동 중 하나를 선택하게 된다.
• 각 선택에 따라 경로를 추적해서 진행해나가야 한다.
  => 여기서 BFS처럼 이동하고 있음을 알 수 있다.
• BFS는 한 단계씩 동시에 진행하기 때문에 언제든 k에 도착한다면 그 때의 시간이 최소가 된다. 바로 함수를 종료한다

2. 나의 풀이

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 100001
using namespace std;

int n, k;
queue<int> q;
int timearr[MAX];

void BFS(int num) {
	q.push(num);
	timearr[num] = 1;

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

		if (next == k)	return;

		if (next - 1 >= 0 && timearr[next - 1] == 0) {
			q.push(next - 1);
			timearr[next - 1] = timearr[next] + 1;
		}
		if (next + 1 <= 100000 && timearr[next+1] == 0) {
			q.push(next + 1);
			timearr[next + 1] = timearr[next] + 1;
		}
		if (next *2 <= 100000 && timearr[next*2] == 0) {
			q.push(next*2);
			timearr[next*2] = timearr[next] + 1;
		}
	}
}

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

	cin >> n >> k;

	BFS(n);
	cout << timearr[k]-1 << "\n";
	return 0;
}

3. 유사한 문제

https://velog.io/@jeongopo/%EB%B0%B1%EC%A4%80-2146-%EB%8B%A4%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0

2146 다리만들기 (BFS)

https://velog.io/@jeongopo/%EB%B0%B1%EC%A4%80-7576-%ED%86%A0%EB%A7%88%ED%86%A0
7576 토마토 (BFS)