13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
// 큐
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
bool c[1000000];
int d[1000000];
int MAX = 1000000;
int main() {
int n, m;
cin >> n >> m;
c[n] = true;
d[n] = 0;
queue<int> q;
queue<int> next_queue;
q.push(n);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now*2 < MAX) {
if (c[now*2] == false) {
q.push(now*2);
c[now*2] = true;
d[now*2] = d[now];
}
}
if (now-1 >= 0) {
if (c[now-1] == false) {
next_queue.push(now-1);
c[now-1] = true;
d[now-1] = d[now] + 1;
}
}
if (now+1 < MAX) {
if (c[now+1] == false) {
next_queue.push(now+1);
c[now+1] = true;
d[now+1] = d[now] + 1;
}
}
if (q.empty()) {
q = next_queue;
next_queue = queue<int>();
}
}
cout << d[m] << '\n';
return 0;
}
// 덱
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
bool c[1000000];
int d[1000000];
int MAX = 1000000;
int main() {
int n, m;
cin >> n >> m;
c[n] = true;
d[n] = 0;
deque<int> q;
q.push_back(n);
while (!q.empty()) {
int now = q.front();
q.pop_front();
if (now*2 < MAX) {
if (c[now*2] == false) {
q.push_front(now*2);
c[now*2] = true;
d[now*2] = d[now];
}
}
if (now-1 >= 0) {
if (c[now-1] == false) {
q.push_back(now-1);
c[now-1] = true;
d[now-1] = d[now] + 1;
}
}
if (now+1 < MAX) {
if (c[now+1] == false) {
q.push_back(now+1);
c[now+1] = true;
d[now+1] = d[now] + 1;
}
}
}
cout << d[m] << '\n';
return 0;
}'Problem set' 카테고리의 다른 글
| [백준] 1991 트리 순회 (0) | 2021.02.20 |
|---|---|
| [백준] 1261 알고스팟 (0) | 2021.02.20 |
| [백준] 14226 이모티콘 (0) | 2021.02.20 |
| [백준] 13913 숨바꼭질 4 (0) | 2021.02.20 |
| [백준] 1697 숨바꼭질 (0) | 2021.02.20 |