https://www.acmicpc.net/problem/12761
12761번: 돌다리
동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대
www.acmicpc.net
|
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
|
#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int>> Q;
bool visit[100001];
int main() {
int a, b, n, m;
int move[3];
cin >> a >> b >> n >> m;
move[0] = 1, move[1] = a, move[2] = b;
visit[n] = true;
Q.push(make_pair(n, 0));
while (!Q.empty()) {
int p = Q.front().first, t = Q.front().second;
Q.pop();
if (p == m) {
cout << t << '\n';
break;
}
for (int i = 0; i < 3; i++) {
if (p + move[i] <= 100000 && !visit[p + move[i]]) {
Q.push(make_pair(p + move[i], t + 1));
visit[p + move[i]] = true;
}
if (p - move[i] >= 0 && !visit[p - move[i]]) {
Q.push(make_pair(p - move[i], t + 1));
visit[p - move[i]] = true;
}
}
if (p * a <= 100000 && !visit[p * a]) {
Q.push(make_pair(p * a, t + 1));
visit[p * a] = true;
}
if (p * b <= 100000 && !visit[p * b]) {
Q.push(make_pair(p * b, t + 1));
visit[p * b] = true;
}
}
return 0;
}
|
cs |
간단한 BFS 문제였다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 18405 경쟁적 전염 (0) | 2020.11.19 |
|---|---|
| 백준 온라인 저지 7576 토마토 (0) | 2020.11.18 |
| 백준 온라인 저지 2178 미로 탐색 (0) | 2020.11.16 |
| 백준 온라인 저지 5430 AC (0) | 2020.11.14 |
| 백준 온라인 저지 (BOJ) 10799 쇠막대기 (0) | 2020.11.13 |
