Hide And Seek!

12851.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
#include <string>
#define endl '\n'
#define point pair<int, int>
using namespace std;

class HS {
private:
    const int MAX = 100001;
    int N, K;
    int cnt = 0;
    vector<int> visit;
public:
    HS() {
        this->input();
        if (this->N not_eq this->K) this->calc_bfs();
        else this->cnt++; //N과 K가 같을경우
        this->output();
    }

    void input() { //init.
        cin >> this->N >> this->K;
        this->visit = vector<int>(this->MAX);
    }
    void calc_bfs() {
        queue<int> q;
        q.push(this->N);

        int sec = 0; //queue의 깊이
        bool chk = false;
        while (not q.empty()) {
            sec++;
        
            int qSize = q.size(); //깊이단위 탐색
            for (int i = 0; i < qSize; i++) {
                int cur = q.front(); visited(cur) = sec; q.pop();

                for (const int& d : { cur, 1, -1 } ) {
                    int next = cur + d;
                    if (next == this->K) {
                        cnt++;
                        chk = true; //이번깊이에서 발견체크
                    }
                    if (this->isSafe(next) and (not this->visited(next))) {
                        q.push(next);
                    }
                }
            }
            if (chk) {// 탐색종료
                visited(this->K) = sec;
                break;
            }
        }
    }
    void output() {
        cout << this->visited(this->K) << endl;
        cout << this->cnt << endl;
    }

    bool isSafe(const int& p) {
        return 0 <= p and p < this->MAX;
    }
    int& visited(const int& p) {
        return this->visit[p];
    }
};

int main(void) {
    ios_base::sync_with_stdio(false);

    HS hideandseek;

    return 0;
}

13549.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
#include <string>
#define endl '\n'
#define point pair<int, int>//first:distance, second:point
using namespace std;

point operator+(const point& p1, const point& p2) {
    return point(p1.first + p2.first, p1.second + p2.second);
}

class HS {
private:
    const int MAX = 100005;
    int N, K;
    vector<bool> visit;
    vector<int> dist;
public:
    HS() {
        this->input();
        this->clac_dijkstra();
        this->output();
    }

    bool isSafe(const int& p) {
        return 0 <= p and p < MAX;
    }

    void input() {
        cin >> this->N >> this->K;
        this->visit = vector<bool>(MAX);
        this->dist = vector<int>(MAX, MAX);
    }
    void clac_dijkstra() {
        //다른 숨바꼭질 문제와 달리 순간이동하면 0초가 걸린다.
        //따라서 bfs로 문제풀이가 되지 않는다...
        //(bfs로 하려면 걸리는 시간이 다 동일해야 한다.)
        //(dijkstra에서 걸리는 시간이 다 동일하면 bfs로 풀어도된다..!)
        //dijkstra기법으로 문제를 푼다. 0초걸리는 것을 먼저다 탐색하기위해.
        priority_queue<point, vector<point>, greater<point>> pq;
        pq.push(point(0, this->N));
        dist[this->N] = 0;

        while (not pq.empty()) {
            point cur;

            do { //queue가 비거나 방문한 곳이면 다시 뽑는다.
                cur = pq.top();
                pq.pop();
            } while (not pq.empty() and visit[cur.second]);
            if (visit[cur.second]) break;
        
            visit[cur.second] = true;
            if (cur.second == this->K) return;

            const point diff[3] = { point(0, cur.second), point(1, 1), point(1, -1) };
            for (auto& d : diff) {
                point next = cur + d;
                if  (isSafe(next.second) and next.first < dist[next.second]) {
                    dist[next.second] = next.first;
                    pq.push(next);
                }
            }
        }
    }
    void output() {
        cout << this->dist[this->K];
    }

};

int main(void) {
    ios_base::sync_with_stdio(false);

    HS hideandseek;

    return 0;
}

13913.cpp

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n' 
using namespace std;

class HS {
private:
    const int MAX = 100001;
    int N, K;
    vector<int> visited;
    vector<int> previous; //이전위치 기록용
public:
    void solve(void) {
        this->input();
        this->calc_bfs();
        cout << this->visited[this->K] - 1 << endl; 
        this->output(this->K);
    }

    bool isSafe(const int& p) {
        return 0 <= p and p < this->MAX;
    }

    void input(void) {
        cin >> this->N >> this->K;
        visited = previous = vector<int>(this->MAX);
        previous[this->N] = -1;
    }
    void calc_bfs(void) {
        queue<int> q;
        q.push(this->N);
        visited[this->N] = 1;

        while (not q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == this->K) break;
            for (const int& d : { cur, 1, -1 } ) {
                int next = cur + d;
                if (this->isSafe(next) and not visited[next]) {
                    q.push(next);
                    this->visited[next] = this->visited[cur] + 1;
                    this->previous[next] = cur;//이전 위치를 기록
                }
            }
        }
    }
    void output(const int& p) {
        if (p not_eq -1) {
            output(previous[p]);
            cout << p << ' ';
        }
    }
};
 
int main(void) {
    ios_base::sync_with_stdio(false);

    HS HideAndSeek;
    HideAndSeek.solve();
 
    return 0;
}