[BOJ]13913 숨바꼭질 4

• sol1(시간초과): BFS
  전체 경로를 저장해 시간초과
  매우 비효율적인 코드구성

#include <bits/stdc++.h>
using namespace std;
int N, K, ans = INT_MAX;
vector<int> ansvec;
bool visited[100001] = {false,};
struct DATA{
    int x;
    int cnt;
    vector<int> root;
};
void bfs(int n){
    queue<DATA> que;
    vector<int> vec;
    vec.push_back(n);
    visited[n] = true;
    que.push({n, 0, vec});
    while(!que.empty()){
        DATA cur = que.front();
        if(cur.x == K){
            ansvec = cur.root;
            ans = cur.cnt;
            break;
        }
        que.pop();
        int nx;
        int nc;
        vector<int> tmp1 = cur.root;
        nx = cur.x + 1;
        nc = cur.cnt;
        if(!(nx < 0 || nx >= 100001 || visited[nx])) {
            visited[nx] = true;
            tmp1.push_back(nx);
            que.push({nx, nc+1, tmp1});
        }
        vector<int> tmp2 = cur.root;
        nx = cur.x - 1;
        if(!(nx < 0 || nx >= 100001 || visited[nx])) {
            visited[nx] = true;
            tmp2.push_back(nx);
            que.push({nx, nc+1, tmp2});
        }
        vector<int> tmp3 = cur.root;
        nx = cur.x * 2;
        if(!(nx < 0 || nx >= 100001 || visited[nx])) {
            visited[nx] = true;
            tmp3.push_back(nx);
            que.push({nx, nc+1, tmp3});
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K;
    //걷는다 or 순간이동한다.
    bfs(N);
    cout << ans << '\n';
    for(auto i : ansvec) cout << i << ' ';
    return 0;
}

• sol2: 직전정점 기억 BFS
• 중요 포인트1: 직전에 방문한 x의 위치를 visited 배열에 저장한다.
• 중요 포인트2: visited 배열에서 최초의 방문지점을 0으로 설정하면 안된다.
  point 0도 방문할 수 있기 때문
  아래 코드에선 -2를 시작점의 방문 노드로 설정했다.

#include <bits/stdc++.h>
using namespace std;
int N, K, ans = INT_MAX, ansidx = 0;
vector<int> visited(100001, -1);
struct DATA{
    int x;
    int cnt;
};
void bfs(int n){
    queue<DATA> que;
    visited[n] = -2;
    que.push({n, 0});
    while(!que.empty()){
        DATA cur = que.front();
        if(cur.x == K){
            ans = cur.cnt;
            ansidx = cur.x;
            break;
        }
        que.pop();
        int nx;
        int nc;
        nx = cur.x + 1;
        nc = cur.cnt + 1;
        if(!(nx < 0 || nx >= 100001 || visited[nx] != -1)) {
            visited[nx] = cur.x;
            que.push({nx, nc});
        }
        nx = cur.x - 1;
        if(!(nx < 0 || nx >= 100001 || visited[nx] != -1)) {
            visited[nx] = cur.x;
            que.push({nx, nc});
        }
        nx = cur.x * 2;
        if(!(nx < 0 || nx >= 100001 || visited[nx] != -1)) {
            visited[nx] = cur.x;
            que.push({nx, nc});
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K;
    bfs(N);
    cout << ans << '\n';
    deque<int> ansdeq;
    ansdeq.push_front(K);
    while(visited[ansidx] != -2){
        ansdeq.push_front(visited[ansidx]);
        ansidx = visited[ansidx];
    }
    for(auto i : ansdeq) cout << i << ' ';
    return 0;
}