숨바꼭질4

BFS로 문제를풀긴했는데, 사실 시간자체를구하는건 너무나도쉽다.

하지만, 문제가되는건 과정을 어떻게 알수있을지 가 관건이였던문제

 

나같은경우는 진행해 나가면서 +1했는지 -1했는지, *2했는지를 배열하나를 더써서 표식을 남겼고,

끝지점에서 트래킹 해나가면서 벡터를 채우는방식으로 문제를 풀었다.

 

#include<cstdio>
#include<iostream>
#include<queue>

using namespace std;

int su;
bool d[300001];
int dist[300001];
int c[300001];
int little;
vector<int> visit;
int ans;

void bfs(int x) {
	queue<int> q;
	q.push(x);
	d[x] = true;
	dist[x] = 0;
	while (!q.empty()) {
		x = q.front();
		q.pop();
		if (x == little) {
			ans = dist[x];
			return;
		}
		if (x + 1 <= 100000 && d[x + 1] == false) {
			d[x + 1] = true;
			c[x + 1] = 1;
			dist[x + 1] = dist[x] + 1;
			q.push(x + 1);
		}
		if ((2 * x) <= 300000 && d[x * 2] == false) {
			d[x * 2] = true;
			c[2 * x] = 0;
			dist[x * 2] = dist[x] + 1;
			q.push(2 * x);
		}
		if (x - 1 >= 0 && d[x - 1] == false) {
			d[x - 1] = true;
			c[x - 1] = -1;
			dist[x - 1] = dist[x] + 1;
			q.push(x - 1);
		}
		
	}
}

void check(int k) {
	for (int i = 0; i < ans; i++) {
		if (c[k] == 1 && d[k] == true)
		{
			visit.push_back(k - 1);
			k = k - 1;
		}
		else if (c[k] == -1 && d[k] == true)
		{
			visit.push_back(k + 1);
			k = k + 1;
		}
		else if (c[k] == 0 && d[k] == true) {
			visit.push_back(k / 2);
			k = k / 2;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> su >> little;
	bfs(su);
	visit.push_back(little);
	check(little);
	cout << ans << endl;
	for (int i = visit.size()-1; i >= 0; i--) {
		cout << visit[i] << " ";
	}cout << endl;
	
	return 0;
}

 

c배열에서 +1했으면 배열에 1을, -1했으면 -1을, 그리고 *2를하면 0을 남겨서, 끝지점에서 트랙킹하기 편하게 정답을 구성했다.