[백준 13913] 숨바꼭질 4 - C++ / 알고리즘 BFS

문제

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

나의 코드 - 시간초과

#include <iostream>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

vector<int>vec[100001];  //경로 저장
bool visited[100001];  //방문한 곳 표시
queue<int> q;
int n, k, result_time, cnt, sec;

void hide_and_seek() {
	q.push(n);
	visited[n] = 1;
	sec = 1;
	result_time = 0;

	while (!q.empty()) {
		cnt = 0;
		for (int i = 0; i < sec; i++) {
			int now = q.front();
			q.pop();
			if (now == k)
				return;

			if (now - 1 >= 0 && visited[now - 1] == 0) {
				q.push(now - 1);
				visited[now - 1] = 1;
				vec[now].push_back(now - 1);
				cnt++;
			}
			if (now + 1 <= 100000 && visited[now + 1] == 0) {
				q.push(now + 1);
				visited[now + 1] = 1;
				vec[now].push_back(now + 1);
				cnt++;
			}
			if (now * 2 <= 100000 && visited[now * 2] == 0) {
				q.push(now * 2);
				visited[now * 2] = 1;
				vec[now].push_back(now * 2);
				cnt++;
			}
		}
		sec = cnt;
		if (cnt != 0)
			result_time++;
	}
}

int main(void) {
	cin >> n >> k;
	for (int i = 0; i < 100001; i++)
		visited[i] = 0;
	hide_and_seek();
	cout << result_time << '\n';

	int now = k;
	int prev;
	stack<int> stk;
	while (now != n) {
		prev = -1;
		stk.push(now);

		for (int i = 0; i < 100001; i++) {
			for (int s = 0; s < vec[i].size(); s++) {
				if (vec[i][s] == now) {
					prev = i;
					break;
				}
			}
			if (prev == i)
				break;
		}
		now = prev;
	}

	cout << n << " ";
	while (!stk.empty()) {
		cout << stk.top() << " ";
		stk.pop();
	}
}  

예상은 했지만 바로 시간초과가 나왔다.

5 - 4, 6, 10이면 vec[5][0] = 4, vec[5][1] = 6, vec[5][2] = 10 이런식으로 저장하고 일일이 찾으려고 하닌깐 시간초과 발생했다.

벡터로 담아서 일일이 탐색해서 그런 것 같다.

나의 코드 - 이전 경로 저장

#include <iostream>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

vector<int>vec(100001);  //이전 경로 저장
bool visited[100001];  //방문한 곳 표시
queue<int> q;
int n, k, result_time, cnt, sec;

void hide_and_seek() {
	q.push(n);
	visited[n] = 1;
	sec = 1;
	result_time = 0;

	while (!q.empty()) {
		cnt = 0;
		for (int i = 0; i < sec; i++) {
			int now = q.front();
			q.pop();
			if (now == k)
				return;

			if (now - 1 >= 0 && visited[now - 1] == 0) {
				q.push(now - 1);
				visited[now - 1] = 1;
				vec[now - 1] = now;
				cnt++;
			}
			if (now + 1 <= 100000 && visited[now + 1] == 0) {
				q.push(now + 1);
				visited[now + 1] = 1;
				vec[now + 1] = now;
				cnt++;
			}
			if (now * 2 <= 100000 && visited[now * 2] == 0) {
				q.push(now * 2);
				visited[now * 2] = 1;
				vec[now * 2] = now;
				cnt++;
			}
		}
		sec = cnt;
		if (cnt != 0)
			result_time++;
	}
}

int main(void) {
	cin >> n >> k;
	for (int i = 0; i < 100001; i++)
		visited[i] = 0;
	hide_and_seek();
	cout << result_time << '\n';

	int now = k;
	int prev;
	stack<int> stk;
	while (now != n) {
		stk.push(now);
		prev = vec[now];
		now = prev;
	}

	cout << n << " ";
	while (!stk.empty()) {
		cout << stk.top() << " ";
		stk.pop();
	}
}

생각을 전환해서 단순히 자신의 이전 경로만 저장하면 거슬러 올라가기 편하므로

vec[자신위치] = 자신 위치의 이전 경로;