[백준 알고리즘]/[C++]
1697번 숨바꼭질 | BFS | Baekjoon BOJ 백준 1697 C++ 코드, 해설, 풀이
말하는펭귄
2021. 2. 1. 09:55
728x90
반응형
이번 포스팅은 백준 1697번 숨바꼭질입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 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
|
//백준1697 숨바꼭질
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 100001;
int N, K;
bool visited[MAX] = { 0, };
int path[MAX];
queue<int> q;
void printPath() {
cout << "[PATH]" << endl;
for (int i = N; i <= K; i++) {
printf("%2d ", i);
}
printf("\n");
for (int i = N; i <= K; i++) {
printf("%2d ", path[i]);
}
printf("\n");
}
void BFS(int v) {
path[v] = 0;
visited[v] = true;
q.push(v);
while (!q.empty()) {
int w = q.front();
if (w == K) break;
q.pop();
if (visited[w + 1] == 0 && w + 1 >= 0 && w + 1 < MAX) {
visited[w + 1] = true;
q.push(w + 1);
path[w + 1] = path[w] + 1;
}
if (visited[w - 1] == 0 && w - 1 >= 0 && w - 1 < MAX) {
visited[w - 1] = true;
q.push(w - 1);
path[w - 1] = path[w] + 1;
}
if (visited[w * 2] == 0 && w * 2 >= 0 && w * 2 < MAX) {
visited[w * 2] = true;
q.push(w * 2);
path[w * 2] = path[w] + 1;
}
}
}
int main() {
cin >> N >> K;
BFS(N);
//printPath();
cout << path[K];
}
|
cs |
728x90
반응형