[ 백준-13549번 / 다익스트라 / BFS ] 숨바꼭질3

1. 문제

---

13549번: 숨바꼭질 3

문제

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

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

입력

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

출력

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

예제 입력 1 복사

5 17

예제 출력 1 복사

2

 

 

 

 

2. 소스코드

---

1회차 - 2020/05/03

2020/05/11 - [알고리즘/PS] - [ 백준 - 1697 / BFS ] 숨바꼭질

의 후속 문제

 

- 1697과 다르게 2배로 이동할때는 시간이 소모되지 않는다. 즉, 이는 가중치가 0인 간선을 의미한다.

- BFS는 모든 가중치가 같다는 전제하에 사용할 수 있다. 따라서, 이 문제에는 BFS를 적용할 수 없다.

- 가능한 풀이는 3가지 정도이다.

 1. 다익스트라

 2. 0-1 BFS : 큐 대신 덱을 사용하고, 가중치가 0인 간선은 덱의 앞에 삽입.

 3. 2배를 별도의 간선으로 처리하지 않고, +-1 좌표를 큐에 삽입할 때, 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

 

- 2번을 이용한 풀이

#include <cstdio>
#include <deque>
#define MAX 100000
using namespace std;

int n, k;
int visited[MAX + 1];
deque<pair<int,int>> que;

int main() {
	scanf("%d %d", &n, &k);
	que.push_back({ n, 0 });
	visited[n] = 1;
	while (!que.empty())
	{
		auto cur = que.front(); que.pop_front();
		int pos = cur.first;
		int depth = cur.second;

		if (pos == k) {
			printf("%d\n", depth);
			return 0;
		}

		//가중치가 0인 간선을 먼저 처리해야한다.
		if (pos * 2 <= MAX and !visited[pos * 2]) {
			visited[pos * 2] = 1;
			//가중치가 0인 간선은 deque의 앞에 넣어 먼저 처리한다.
			que.push_front({ pos * 2, depth });
		}
		
		if (pos - 1 >= 0 and !visited[pos - 1]) {
			visited[pos - 1] = 1;
			que.push_back({ pos - 1, depth + 1 });
		}

		if (pos + 1 <= MAX and !visited[pos + 1]) {
			visited[pos + 1] = 1;
			que.push_back({ pos + 1, depth + 1 });
		}
	}
	return 0;
}