백준 13549 숨바꼭질 3

1.  문제 링크

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

13549번: 숨바꼭질 3

 

2.  풀이

지금 위치에서 갈 수 있는 경우의 수와 비용은 아래와 같다.

1. 이동: (지금 위치) * 2       비용: 0 
2. 이동: (지금 위치) - 1       비용: 1
3. 이동: (지금 위치) +1       비용: 1

위 조건에서, N -> K로 이동하는 최단거리를 구하면 되는 문제이다. 

 

#include <iostream>
#include <queue>

using namespace std;

class Element {
public:
	int pos, weight;
	Element() {};
	Element(int pos, int weight) {
		this->pos = pos;
		this->weight = weight;
	}
};

struct compare {
	bool operator()(Element& e1, Element& e2) const {
		return e1.weight > e2.weight;
	}
};

const int	INTMAX = 2000000000;
int			N, K;
bool		visited[100001];
int			dist[100001];

void InputAndInit() {
	cin >> N >> K;
	for (int i = 0; i < 100001; i++) {
		visited[i] = false;
		dist[i] = INTMAX;
	}
}

int main()
{
	InputAndInit();
	priority_queue<Element, vector<Element>, compare> pq;
	pq.push({ N, 0 });
	dist[N] = 0;
	while (!pq.empty()) {
		Element currentE = pq.top(); pq.pop();
		visited[currentE.pos] = true;
		if (currentE.pos == K)
			break;
		int next = currentE.pos * 2;
		if (next >= 0 && next < 100001 && !visited[next]) {
			if (dist[next] > dist[currentE.pos]) {
				pq.push({ next,dist[currentE.pos] });
				dist[next] = dist[currentE.pos];
			}
		}
		int tmp[2] = { currentE.pos - 1, currentE.pos + 1 };
		for (int i = 0; i < 2; i++) {
			int next = tmp[i];
			if (next >= 0 && next < 100001 && !visited[next]) {
				if (dist[next] > dist[currentE.pos] + 1) {
					pq.push({ next,dist[currentE.pos] + 1 });
					dist[next] = dist[currentE.pos] + 1;
				}
			}
		}
	}
	cout << dist[K] << "\n";
}