백준 13549 숨바꼭질 3 풀이 (BFS & deque)

사용언어

Visual studio 2019 C++

분류

BFS (deque)

잘못된 풀이

처음봤을 때에는 일반적인 BFS알고리즘으로 알고 queue로 풀게되었다.
그러면 문제의 예제는 풀리게 되지만
ex) N: 5 K: 100000 와 같은 예제에서는 풀리지 않게된다.

#include <iostream>
#include <queue>

#define MAX 100001
#define endl "\n"
using namespace std;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int minSecond(int N, int K) {
	queue<pair<int, int>> q;
	int result = 0;
	q.push(make_pair(N, 0));

	while (!q.empty()) {
		int d = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (d == K) {
			result = cost;
			break;
		}

		if (d * 2 < MAX)
			q.push(make_pair(d * 2, cost));
		q.push(make_pair(d - 1, cost + 1));
		if (d + 1 < MAX)
			q.push(make_pair(d + 1, cost + 1));
	}

	return result;
}

int main() {
	init();
	int N, K;
	cin >> N >> K;

	cout << minSecond(N, K) << endl;
}

Deque

deque<int> dq;

dq.push_front(3); // 첫 번째 원소 앞에 3 삽입
dq.push_back(4); // 마지막 원소 뒤에 4 삽입

dq.front(); // 첫번째 원소참조
dq.back(); // 마지막 원소참조

dq.pop_front(); // 첫 번째 원소제거
dq.pop_back(); // 마지막 원소제거

[13549 풀이]

13549 풀이 바로가기