Skip to content

Instantly share code, notes, and snippets.

@tiger1710 tiger1710/12851.cpp
Last active Mar 3, 2020

Embed
What would you like to do?
Hide And Seek!
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.