백준 No.13913 [숨바꼭질4]

Baekjoon Online Judge No.13913 [숨바꼭질4]

---

 Problem 

13913번: 숨바꼭질 4

---

 Code 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
const int MAX = 100000;
 
struct movement {
    int pos;
    int time;
    vector<int> trace;
};
 
queue<movement> Q;
int subin, dong;
vector<bool> visited(MAX + 1, false);
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> subin >> dong;
 
    if (dong <= subin) {
        cout << subin - dong << '\n';
 
        for (int i = subin; i >= dong; i--)
            cout << i << ' ';
 
        return 0;
    }
 
    vector<int> init;
    Q.push({ subin, 0, init});
    visited[subin] = true;
 
    while (!Q.empty()) {
        movement temp = Q.front();
        Q.pop();
 
        int& POS = temp.pos;
        int& TIME = temp.time;
        vector<int>& TRACE = temp.trace;
 
        TRACE.push_back(POS);
 
        visited[POS] = true;
 
        if (POS == dong) {
            cout << TIME << '\n';
 
            for (auto e : TRACE) cout << e << ' ';
 
            break;
        }
        
        if (2 * POS <= MAX && !visited[2 * POS]) Q.push({ 2 * POS, TIME + 1, TRACE});
        if (POS < MAX && !visited[POS + 1]) Q.push({ POS + 1, TIME + 1, TRACE});
        if (POS > 0 && !visited[POS - 1]) Q.push({ POS - 1, TIME + 1, TRACE});
    }
}

---

 How to solve 

  아래 "둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다." 가 없으면 그냥 일반적인 BFS방식으로 풀면 됐다. 하지만 문제에서 저렇게 요구하므로, #9 line 처럼 movement struct 를 선언하여 trace 를 남겨둘 수 있도록 하였다. 방문한 지점은 #47 line 에서 입력이 된다.

 

  처음엔 #26 ~ #33 line 을 적어주지 않고 제출을 했었다가 시간초과가 났다. 동생이 수빈이보다 뒤에 있는 경우엔, 순간이동이고 뭐고 할거 없이 그냥 뒤로만 가야하므로 BFS를 통해서 계산하면 엄청난 시간 손해, 메모리 손해가 난다. 따라서 저렇게 동생이 수빈이보다 뒤에 있는 경우를 먼저 따져보고 처리해주었다.