반응형
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지
www.acmicpc.net
가장 빠른 가장 최단거리 문제는 BFS다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int N, K;
int mytime = 987654321;
bool check[100001];
void BFS(int n,int k) {
queue <pair<int,int>> q;
q.push(pair<int,int>(n,0));
int locate;
int current;
while (!q.empty()) {
locate = q.front().first;
current = q.front().second;
check[locate] = true;
q.pop();
if (!(current >= mytime)) {
if (locate == k) {
mytime = min(mytime, current);
}
else if (locate > k) {
if (check[(locate - 1)] == false) {
q.push(pair<int, int>(locate - 1, current + 1));
}
}
else {
if (locate * 2 <= 100000) {
if (check[locate * 2] == false) {
q.push(pair<int, int>(locate * 2, current + 1));
}
}
if (check[locate + 1] == false) {
q.push(pair<int, int>(locate + 1, current + 1));
}
if (locate != 0) {
if (check[locate - 1] == false) {
q.push(pair<int, int>(locate - 1, current + 1));
}
}
}
}
}
}
int main(void) {
cin >> N >> K;
BFS(N, K);
cout << mytime << endl;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'ProgramSoliving' 카테고리의 다른 글
| 백준 : 1931* (0) | 2019.12.21 |
|---|---|
| 백준 : 2206 * (0) | 2019.12.19 |
| 백준 : 7569 (0) | 2019.12.17 |
| 백준 : 7576 (0) | 2019.12.17 |
| 백준 : 1012 (0) | 2019.12.16 |