C++ / 백준 / 1697 / 숨바꼭질

문제

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

1697번: 숨바꼭질

문제풀이

BFS를 이용해 풀었다.

방문 함수를 만들어 같은 곳을 재방문하지 않도록 했다.

2열짜리 큐를 만들어 현재 위치, 몇번 이동했는지를 나타낸다.

점은 100,000까지 있으므로 더 넘지 못하고, 각각 제한을 걸어 효율적으로 이동할 수 있게 한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<bool>visit(100001, false);
int K;

void Move(int x, int sec) {
	queue<pair<int, int>> q;
	q.push({ x,sec });
	while (!q.empty()) {
		x = q.front().first;
		sec = q.front().second;
		q.pop();
		if (x == K) {
			cout << sec;
			return;
		}		
		else if (!visit[x]) {
			visit[x] = true;
			if (x * 2 <= 100000 && x < K)
				q.push({ x * 2,sec + 1 });
			if (x < K)
				q.push({ x + 1,sec + 1 });
			if (x > 0)
				q.push({ x - 1,sec + 1 });
		}
	}	
}

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

	int N = 0;
	cin >> N >> K;
	Move(N, 0);
}