백준 13913 숨바꼭질 4 풀이 (BFS & deque)

사용언어

Visual studio 2019 C++

분류

BFS (deque)

이 문제는 13549 문제와 유사하지만 경로까지 구해야 되는 부분이 변수였다.
그래서 그 부분을 vector를 사용하여 다음숫자의 vector에 전 숫자를 넣어서 횟수를 구한 이후 해결했다.

Deque

deque<int> dq;

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

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

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

[13913 풀이]

#include <iostream>
#include <deque>
#include <vector>
#include <stack>

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

int N, K;
int visited[MAX];
vector<int> parent[MAX];

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

int dynamic() {
	deque<pair<int, int>> dq;
	dq.push_back(make_pair(N, 0));
	visited[N] = true;

	while (!dq.empty()) {
		int cost = dq.back().second;
		int distance = dq.back().first;
		dq.pop_back();

		if (distance == K)
			return cost;

		int gogo[3] = { distance * 2, distance - 1, distance + 1 };

		for (int i = 0; i < 3; i++) {
			if (gogo[i] < MAX && gogo[i] >= 0) {
				if (!visited[gogo[i]]) {
					visited[gogo[i]] = true;

					if (gogo[i] == distance * 2) {
						dq.push_back(make_pair(gogo[i], cost + 1));
						parent[gogo[i]].push_back(distance);
					}
					else {
						dq.push_front(make_pair(gogo[i], cost + 1));
						parent[gogo[i]].push_back(distance);
					}
				}
			}
		}
	}
}

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

	cout << dynamic() << endl;

	int a = K;

	deque<int> d;
	d.push_back(a);
	while (a != N) {
		a = parent[a].front();
		d.push_back(a);
	}
	
	while (!d.empty()) {
		int c = d.back();
		cout << c << " ";
		d.pop_back();
	}
	cout << endl;
}