[C++][백준 1697][BFS DFS] 숨바꼭질 :: seoftware

문제

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

1697번: 숨바꼭질

소스코드

#include <queue>
#include <iostream>
using namespace std;
int x, y; //x는 수빈, y는 동생 좌표
int trace[100001];
queue<int> q;
int bfs() {
	q.push(x);
	trace[x] = 1;
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		if (p == y) return trace[p] -1 ;

		if (p - 1 >= 0 && trace[p - 1] == 0) {
			q.push(p - 1);
			trace[p - 1] = trace[p] + 1;
		}
		if (p + 1 <= 100000 && trace[p + 1] == 0) {
			q.push(p + 1);
			trace[p + 1] = trace[p] + 1;
		}
		if (p * 2 <= 100000 && trace[2*p] == 0) {
			q.push(p * 2);
			trace[p * 2] = trace[p] + 1;
		}
	}
}
int main(void) {
	cin >> x >> y;
	
	cout << bfs();

	return 0;
}

숨바꼭질도 토마토 문제와 마찬가지고 이전 값을 이용하는 문제다!