[백준] 13549 숨바꼭질 3 - 0-1 BFS

문제

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

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

입력

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

출력

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

 

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, K,d[200001];
int main() {
	FAST;
	memset(d,0x3f,sizeof(d));
	deque<int>dq;
	cin >> N >> K;
	dq.push_back(N);
	d[N] = 0;
	while (!dq.empty()) {
		auto f = dq.front();
		dq.pop_front();
		if (f == K) {
			cout << d[f];
			break;
		}
		int doub = f * 2;
		if (doub != N && doub <= 200000 && d[doub] > d[f] + 1) {
			d[doub] = d[f];
			dq.push_front(doub);
		}
		int le = f - 1, ri = f + 1;
		if (le >= 0 && d[le] > d[f] + 1) {
			d[le] = d[f] + 1;
			dq.push_back(le);
		}
		if (ri <= 200000 && d[ri] > d[f] + 1) {
			d[ri] = d[f] + 1;
			dq.push_back(ri);
		}
	}
}

0-1 BFS 알고리즘은 평범한 bfs에 간선의 가중치가 1or0일 때 사용할 수 있는 기법입니다.

 

큐를 사용하는 일반적인 BFS와 달리, 

0-1 BFS는 덱큐를 사용합니다.

덱큐는 앞과 뒤로 데이터를 넣고 뺄 수 있습니다.

 

간선의 가중치가 1인경우, 덱큐의 맨 앞에 데이터를 넣습니다.

간선의 가중치가 0인경우, 덱큐의 맨 뒤에 데이터를 넣습니다.

 

0초 뒤에 2*X만큼 이동할 수 있기 때문에, 각 정점에서 2배만큼의 거리를 움직이는 간선은 가중치가 1이고,

앞뒤로 한칸씩 움직일 때눈 간선의 가중치가 0입니다.

 

다익스트라 알고리즘과 마찬가지로,

[다음 노드까지 이동거리] > [현재 노드까지 이동거리] + [현재노드에서 다음노드까지 거리] 인 경우,

다음노드까지 거리를 갱신합니다.