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

 

모든 경우의 수를 담고 찾는다.

 

#define MIN 0
#define MAX 100000

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

/*
동생이 자신보다 작은 곳에 위치할 때 탐색할 필요가 없다.
N < 0 일 때, 탐색할 필요가 없다.
N = K 여도 탐색할 필요가 없다.
N < 10만 이어도 더 넣을 필요가 없다.
visit한 것은 탐색할 필요가 없다.
N*2, N+1도 10만이 넘으면 탐색할 필요가 없다.
*/


int check[MAX+1];
int main() {
	int N, K;

	cin >> N >> K;

	int pos;
	int cnt=0; //몇 초인지 세어야 한다.
	queue<pair<int,int>> q;


	//현 위치와 시간을 넣는다.
	
	q.push(make_pair(N, cnt));
	check[N] = 1;

	while (!q.empty()) {
		pos = q.front().first;
		cnt = q.front().second;
		q.pop();
		
		//cout << pos <<","<<cnt<< "->";

		if (pos == K) { //찾았다 요놈
			break;
		}

		if (pos + 1 <= MAX && check[pos + 1] == 0) {
			check[pos + 1] = 1;
			q.push(make_pair(pos + 1, cnt + 1));
		}

		if (pos - 1 >= MIN && check[pos - 1] == 0) {
			check[pos - 1] = 1;
			q.push(make_pair(pos - 1, cnt + 1));
		}

		if (pos*2 <= MAX && check[pos*2] == 0) {
			check[pos*2] = 1;
			q.push(make_pair(pos*2, cnt + 1));
		}

	}

	cout << cnt;

	return 0;
}

 

#include<iostream>
#include<queue>
using namespace std;
#define MIN 0
#define MAX 1000000
int N, K;
queue<pair<int,int>> q;
int visit[MAX+1];

void bfs(int x) {

	q.push(make_pair(x,0));

	while (!q.empty()) {
		int cx = q.front().first;
		int ct = q.front().second;
		visit[cx] = 1;
		q.pop();

		if (cx == K) {
			cout << ct;
			return;
		}
		if (cx - 1 >= MIN && visit[cx - 1] == 0) q.push(make_pair(cx - 1, ct + 1));
		if (cx + 1 <= MAX && visit[cx + 1] == 0) q.push(make_pair(cx + 1, ct + 1));
		if (cx * 2 <= MAX && visit[cx * 2] == 0) q.push(make_pair(2 * cx, ct + 1));
		

	}
}

int main() {

	cin >> N >> K;
	bfs(N);
    
	return 0;
}