BFS가 적절하다.BFS 풀이 방법으로, 도착지점에 가장 먼저 도착할 때 최단경로가 보장되기 때문에, 도착 지점에 도달할 때까지 경로를 기록해 두어야 한다.
처음에는 경로를 이동할 때마다 현재까지 방문한 지점을 배열 형태(vector)에 저장하여 전달하는 방법을 떠올렸다.
따라서 아래와 같이 코드를 작성하였는데, 시간초과가 떴다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
queue<vector<int>> q;
bool visited[100001];
const int MAX = 100000;
vector<int> bfs(int start, int end) {
visited[start] = true;
vector<int> route;
route.push_back(start);
q.push(route);
while (!q.empty()) {
route = q.front(); // 현재 지점까지 도달하는 데 지나온 경로
int now = route[route.size() - 1]; // 현재 살펴볼 지점은 경로의 맨 마지막 요소
q.pop();
if (now == end) { // 끝점까지 도달했다면,
return route; // 최단 경로 리턴
}
if (now + 1 <= MAX && !visited[now + 1]) {
visited[now + 1] = true;
route.push_back(now + 1); // 바로 다음에 방문할 지점을 푸시한 채로 q에 푸시
q.push(route);
route.pop_back(); // 푸시한 이후에는 pop
}
if (now - 1 >= 0 && !visited[now - 1]) {
visited[now - 1] = true;
route.push_back(now - 1);
q.push(route);
route.pop_back();
}
if (2 * now <= MAX && !visited[2 * now]) {
visited[2 * now] = true;
route.push_back(2 * now);
q.push(route);
route.pop_back();
}
}
}
int main() {
int n, k;
cin >> n >> k;
vector<int> result;
result = bfs(n, k);
cout << result.size() - 1 << '\\n';
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << ' ';
}
cout << '\\n';
return 0;
}
따라서 앞선 방법처럼 경로 배열을 큐에 푸시하는 방법 말고 다른 방법을 찾아야 한다.
전체 노드 갯수 만큼의 배열을 만들고, 인덱스 값에 해당하는 노드를 방문하기 이전에 어느 노드를 방문했는지 저장하는 방법이 떠올랐다.
→ 가령, 10번 노드를 방문하기 전에 5번 노드를 방문했다면, prev_loc[10] == 5 가 되는 것이다.
이 방법을 사용하게 되면 한 번 탐색을 할 때마다 노드를 벡터에 푸시하지 않아도 되고, 또 크기가 고정되어있는 배열의 값만 변경해주면 되기 때문에, 메모리나 시간적인 측면에서 더 효율적일 방안이 될 것이다.