[백준] 13549번 : 숨바꼭질 3 C++ 풀이

접근

3가지의 선택: -1, +1, x2

그리고 가장 작은 weight를 가지는 길을 찾아야 한다.

그래서 일단은 너비 우선 탐색을 선택했다. 왜냐하면 가장 짧은 길을 탐색하기 위해서 너비를 우선으로 탐색해야 하기 때문이다. 그렇게 하기 위해 큐를 이용하기로 했다. 그리고 가중치가 0,1 로 다르기 때문에 다익스트라 알고리즘을 이용하기로 했다.

전략

큐에 n의 위치를 넣고, 3가지 선택 중에 선택을 할 수 있는 조건을 만족하면(범위 내 이고, 가중치가 더 작으면)

선택을 하여 큐에 삽입을 한다. 이때, 중요한 건 선택 순서가 중요한데,

2배를 하면 가중치가 0이기 때문에, 3가지 중에 2배를 하는 것을 먼저 선택하도록 순서를 정해야, 최소의 가중치를 구할  수 있다. 방향성이 음수로 가는 방향은 -1 밖에 없으므로, n보다 작은 부분은 무조건적으로 -1만 선택하는게 가장 빠르다. k>n 이면, n부터 양의 방향으로 가는 위치는 +1 가 증가 하는 속도 보다 *2 하는게 더 빠르므로, 미리 2배씩을 하고 시작하지 않아도, 가장 먼저 2배가 마지막 범위 까지 먼저 도착한다.

따라서 *2를 먼저 선택하고, 그 뒤에 남은 두 개를 선택하도록 한다.

가장 먼저 찾는 것이 있으면 그것이 가장 작은 가중치이다.

 

구현

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


int n, k;

int p[100001]{};
int w = 0;

int min_w = 1000000;

void shortest() {
	queue<int> q;
	q.push(n); 
	p[n]=0;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();

		if (cur == k) {
			min_w = p[cur];
			return;
		}
		if (cur * 2 < 100001  && p[cur * 2] > p[cur]) {
			p[cur * 2] = p[cur];
			q.push(cur * 2);
		}
		 
		if (cur + 1 < 100001 && p[cur + 1] > p[cur] + 1) {
			p[cur + 1] = p[cur] + 1;
			q.push(cur + 1);
		}

		if (cur - 1 >= 0 && p[cur - 1] > p[cur] + 1) {
			p[cur - 1] = p[cur] + 1;
			q.push(cur - 1);
		}

		
	}
}

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

	cin >> n >> k;

	for (int i = 0; i < 100001; i++) {
		p[i] = 1000000;
	}

	shortest();

	cout << min_w << '\n';
	return 0;
}