13549 - 숨바꼭질

첫번째 풀이

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;


int visited[100001];

void bfs(int N, int K) {
	queue <int >q;
	q.push(N);
	visited[N] = 0;
	while (!q.empty()) {
		int cur_node = q.front();
		q.pop();
		// 이동하기
		for (int i = cur_node ; i <= 100000; i = 2 * i) {
			if (2 * cur_node <= 100000 && visited[2 * cur_node] == -1) {
				q.push(2 * cur_node);
				visited[2 * cur_node] = visited[cur_node];
			}
		}
		

		if (cur_node + 1 <= 100000 && visited[cur_node +1]==-1) {
			q.push(cur_node + 1);
			visited[cur_node + 1] = visited[cur_node] + 1;
		}
		if (cur_node - 1 >=0 && visited[cur_node - 1] == -1) {
			q.push(cur_node - 1);
			visited[cur_node - 1] = visited[cur_node] + 1;
		}
		
		if (cur_node == K) { break; }
	}
}


int main() {
	memset(visited, -1, sizeof(visited));
	int N;
	int K;

	cin >> N >> K;
	
	bfs(N, K);

	cout << visited[K] << '\n';
	return 0;
}

시간초과!

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.라는 문제의 조건 때문에 우선순위가 존재하기 때문에 우선순위 큐로 최적의 경로로 해를 구하는게 맞다!

두번째 풀이

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;


int visited[100001];

void bfs(int N, int K) {
	// 가장 빠른 시간을 찾는 것이므로 우선순위큐로 구현한다
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push(make_pair(0,N));
	visited[N] = 0;
	while (!pq.empty()) {
		int time = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();
		

		// 이동하기
		if (2 * cur_node <= 100000 && visited[2 * cur_node] == -1) {
			pq.push(make_pair(time, 2 * cur_node));
			visited[2 * cur_node] = visited[cur_node];
		}

		if (cur_node + 1 <= 100000 && visited[cur_node +1]==-1) {
			pq.push(make_pair(time + 1, cur_node + 1));
			visited[cur_node + 1] = visited[cur_node] + 1;
		}
		if (cur_node - 1 >=0 && visited[cur_node - 1] == -1) {
			pq.push(make_pair(time + 1, cur_node - 1));
			visited[cur_node - 1] = visited[cur_node] + 1;
		}
		
		if (cur_node == K) { break; }
	}
}


int main() {
	memset(visited, -1, sizeof(visited));
	int N;
	int K;

	cin >> N >> K;
	
	bfs(N, K);

	cout << visited[K] << '\n';
	return 0;
}

우선순위를 이용하여 정답!

놓친 점

1. priority_queue<pair<int, int>, greater<int>>pq; (X)
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;(O)

   greater를 사용할 경우, priority_queue는 단순히 int를 비교하여 큰 값이 더 우선순위를 가지게 됩니다. 그러나 pair<int, int>와 같은 복합적인 자료형을 정렬하기 위해서는 greater<pair<int, int>>와 같이 복합적인 자료형에 대한 비교 함수 객체가 필요합니다.
   greater가 아니라 greater<pair<int, int>>를 사용해야 하는 이유는 pair<int, int>의 요소들을 비교하기 위해서입니다.

2. BFS는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요한데 이 문제는 가중치가 달라서 우선순위를 적용해야했다