백준 13913 / 숨바꼭질 4

그냥 가장 빠른 시간만 출력하는 문제였다면 쉬웠지만

경로까지 출력해야되기 때문에 좀 복잡하다.

BFS를 사용해야하는 문제.

경로는 구조체와 벡터를 이용하여 출력해야한다.

위의 방법도 한 방법이긴하나 from배열을 만들어서 어디서왔는지 저장한 다음 

경로를 역순으로 벡터에 모두 넣고 역 출력하는 것이 가장 좋은 방법이다.

자꾸 시간초과가 뜨길래 편법을 썼다

N이 K보다 클때는 뒤로가는 방법밖에 없기 떄문에

그냥 포문돌려서 출력하니 해결됬다.

코드 (벡터를 이용하여 경로를 출력하는 방법)

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
int dist[100001];
int from[100001];
bool check[100001];
 
 
queue<int>q;
 
stack<int>trace;
 
int main() {
 
    int n, k;
 
    cin >> n >> k;
 
 
    dist[n] = 0;
    check[n] = true;
 
    q.push(n);
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        if (now + 1 <= 100000 && check[now + 1] == false) {
            check[now + 1] = true;
            dist[now + 1] = dist[now] + 1;
            from[now + 1] = now;
            q.push(now + 1);
        }
        if (now - 1 >= 0 && check[now - 1] == false) {
            check[now - 1] = true;
            dist[now - 1] = dist[now] + 1;
            from[now - 1] = now;
            q.push(now - 1);
        }
        if (now * 2 <= 100000 && check[now * 2] == false) {
            check[now * 2] = true;
            dist[now * 2] = dist[now] + 1;
            from[now * 2] = now;
            q.push(now * 2);
        }
    }
 
    cout << dist[k] << endl;
 
    int now = k;
    trace.push_back(k);
    while (now != n) {
        now = from[now];
        trace.push_back(now);
    }
 
    reverse(trace.begin(), trace.end());
 
    for (int i = 0; i < trace.size(); i++) {
        cout << trace[i] << " ";
    }
 
 
 
}

코드 (구조체를 이용하여 경로를 출력하는 방법)

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
bool check[100001];
 
struct DATA {
    int x;
    int step;
    vector<int>path;
 
 
};
 
 
int main() {
    
    int n, k;
    queue<DATA>q;
 
 
    cin >> n >> k;
 
    check[n] = true;
 
    DATA s;
    s.x = n;
    s.step = 0;
 
    q.push(s);
    
 
    if (n <= k) {
        while (!q.empty()) {
            DATA d;
            d = q.front();
            q.pop();
 
            int now = d.x;
            int st = d.step;
 
            if (now == k) {
                cout << st << endl;
                d.path.push_back(k);
 
                for (int i = 0; i < d.path.size() - 1; i++) {
                    if (d.path[i] != d.path[i + 1])
                        cout << d.path[i] << " ";
                }
 
                cout << k;
 
                break;
 
 
            }
 
            int a = now - 1;
            int b = now + 1;
            int c = now * 2;
 
            if (a >= 0 && a <= 100000 && check[a] == false) {
                check[a] = true;
                d.x = a;
                d.path.push_back(now);
                d.step = st + 1;
                q.push(d);
            }
            if (b >= 0 && b <= 100000 && check[b] == false) {
                check[b] = true;
                d.x = b;
                d.path.push_back(now);
                d.step = st + 1;
                q.push(d);
 
            }
            if (c >= 0 && c <= 100000 && check[c] == false) {
                check[c] = true;
                d.x = c;
                d.path.push_back(now);
                d.step = st + 1;
                q.push(d);
            }
 
        }
    }
    else {
        cout << n-k << endl;
 
        for (int i = n; i >= k; i--) {
            printf("%d ", i);
            
        }
 
    }
 
}