숨바꼭질 4

코드

[ 시간 초과 코드 ]

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int dx[3] = {-1, 1, 2};
int board[200001];
int ans=-1;
int flag=0;
int DFS(vector<int> l, int depth, int answer, int val)
{
    l.push_back(val);
    if(depth == ans){
        if(val == answer && !flag){
            val = answer;
            for(auto a : l) cout << a << ' ';
            flag=1;
            cout << '\n';
        }
        return 0;
    }else{
        DFS(l,depth+1,answer,val-1);
        DFS(l,depth+1,answer,val+1);
        DFS(l,depth+1,answer,2*val);
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    queue<int> q;
    q.push(N);
    board[N] = 1;
    if(N == K){
        cout << 0 << '\n';
        cout << N << '\n';
        return 0;
    }
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        for(int i=0;i<3;i++)
        {
            int nx;
            if(i != 2) nx = cur + dx[i];
            else nx = cur*dx[i];
            if(nx < 0 || nx >= 200000 || board[nx] ) continue;
            q.push(nx);
            board[nx] = board[cur] + 1;

            if(nx == K){
                ans = board[nx]-1;
                break;
            }
        }
        if(ans != -1) break;
    }
    cout << ans << '\n';
    vector<int> l;
    q.push(N);
    DFS(l,0,K,N);
    return 0;
}

• BFS로 해당 depth를 구한 뒤 DFS로 그 경로 출력해서 해결
• 경로를 일일히 vector에 추가하다보니 시간초과가 난 것 같다

---

[ 정답 ]

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int dx[3] = {-1, 1, 2};
int board[200001];
int parent[200001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    queue<int> q;
    q.push(N);
    board[N] = 1;
    parent[N] = N;
    if(N == K){
        cout << 0 << '\n';
        cout << N << '\n';
        return 0;
    }
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        for(int i=0;i<3;i++)
        {
            int nx;
            if(i != 2) nx = cur + dx[i];
            else nx = cur*dx[i];
            if(nx < 0 || nx >= 200000 || board[nx] ) continue;
            q.push(nx);
            board[nx] = board[cur] + 1;
            parent[nx] = cur;
            if(nx == K){
                cout << board[nx] -1 <<'\n';
                int value=K;
                vector<int> answer;
                /* 지금까지의 경로를 거슬러 올라가며 answer에 추가 */
                while(true)
                {
                    if(value != N){
                        answer.push_back(value);
                        value = parent[value];
                    }
                    else{
                        answer.push_back(N);
                        break;
                    }
                }
                /* answer 뒤집은 후 출력! */
                reverse(answer.begin(), answer.end());
                for(auto a : answer) cout << a << ' ';
                return 0;
            }
        }
    }
    return 0;
}

• key point!
  : 자신의 parent를 저장하는 parent[]를 사용한 후 거슬러 올라가 출력!