[백준 13549] 숨바꼭질3

문제 풀이

 

간단하게 BFS로 작성하고 제출하면 틀렸다고 나온다.

 

수빈이는

0초에 순간이동으로 현재 지점 x -> 2x로 움직일 수 있고,

1초에 -1 혹은 1로 움직일 수 있다.

 

그런데 BFS 라는 알고리즘은 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다.

이 문제 같은 경우는 동일하지 않은 가중치가 존재한다.

 

이러한 문제를 해결하기 위해서는 상식적으로 현재 공간에서 순간이동, 후진, 전진 중 시간 소모가 없는 순간이동부터 하는 것이 최단 경로다. 그런데 어떤 경우에서는 순간 이동보다 후진 혹은 전진이 먼저 큐에서 나올 수 있기 때문에

큐에 넣을 때 간선의 가중치가 훨씬 적은 순간이동부터 최우선으로 넣어야하는 것만 주의하면 된다.

이런 알고리즘을 0-1 BFS라고 한다.

 

0-1 BFS를 구현하는 방법은 여러가지가 있겠지만 deque를 이용해서 간단하게 구현할 수 있다.

가중치가 낮은 순간이동의 경우는 큐의 앞쪽에 넣고

가중치가 높은 후진이나 전진의 경우는 큐의 뒤쪽에 넣어서

최단 경로를 보장할 수 있도록 구현하면 문제를 해결할 수 있다.

 

소스 코드

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

const int MAX = 200002;
int N, K;
bool visit[MAX];

int bfs()
{
	deque<pair<int, int> > dq;
	dq.emplace_back(N, 0);
	visit[N] = true;
	while (!dq.empty())
	{
		int cur = dq.front().first;
		int cnt = dq.front().second;
		dq.pop_front();

		if (cur == K)
		{
			return cnt;
		}

		if (cur * 2 < MAX)
		{
			if (visit[cur * 2] == false)
			{
				visit[cur * 2] = true;
				dq.emplace_front(cur * 2, cnt);
			} 
		}

		if (cur + 1 < MAX)
		{
			if (visit[cur + 1] == false)
			{
				visit[cur + 1] = true;
				dq.emplace_back(cur + 1, cnt + 1);
			}
		}

		if (cur - 1 >= 0)
		{
			if (visit[cur - 1] == false)
			{
				visit[cur - 1] = true;
				dq.emplace_back(cur - 1, cnt + 1);
			}
		}
	}
	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	cout << bfs() << endl;
	return 0;
}