[BOJ] 백준 13913번 : 숨바꼭질4 C++ : 아주정은

문제가 다른 숨바꼭질과 굉장히 비슷하다. 그래서 금방 최소값은 구할수있었는데, 경로를 어떻게 찾을까 생각을 해보았다.

​트리를 그리면 굉장히 쉬운거지만 어떻게 구현을 해야할지 고민을 했다.

음 그냥 무식하게 해보면, 문자 배열을 선언하고, 진행될때마다 어떤 수식을 썻는지 저장을 해준다.

그다음 역추적 방식으로 찾아가주면 된다.

굉장히 코드가 무식하지만, 그래도 원샷원킬했음^^

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[100001];
char mul[100001];
int arr[100001];

//굉장히 무식한 방법같지만 순간 떠오른게 이거여서 해봤다...

int main()
{
	int a, b,i,j,temp;
	cin >> a >> b;
	queue<Que> Q;
	Q.push({ a,0 });
	arr[0] = a;
	vis[a] = true;
	mul[a] = '=';

	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();

		if (cur.x == b) {
			cout << cur.time << endl;
			i = cur.x;
			j = cur.time;
			break;
		}

		if (cur.x * 2 < 100001 and vis[cur.x * 2] == false) {
			Q.push({ cur.x * 2,cur.time+1 });
			vis[cur.x * 2] = true;
			mul[cur.x * 2] = '/';
		}
		if (cur.x + 1 < 100001 and vis[cur.x + 1] == false) {
			Q.push({ cur.x + 1,cur.time + 1 });
			vis[cur.x + 1] = true;
			mul[cur.x + 1] = '-';
		}
		if (cur.x - 1 >= 0 and vis[cur.x - 1] == false) {
			Q.push({ cur.x - 1,cur.time + 1 });
			vis[cur.x - 1] = true;
			mul[cur.x - 1] = '+';
		}
	}
	temp = j;
	while (mul[i] != '=') {//등호가 나올때까지 출력해준다. 곱하기를 했을경우 i를 나누면 그전 숫자가 됨
		if (mul[i] == '/') {
			arr[j] = i;
			i = i / 2;
		}
		else if (mul[i] == '-') {
			arr[j] = i;
			i = i - 1;
		}
		else if (mul[i] == '+') {
			arr[j] = i;
			i = i + 1;
		}
		j--;
	}
	for (int k = 0; k < temp + 1; k++) {//출력해준다.
		cout << arr[k] << " ";
	}
}