반응형
문제 링크: https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
<문제 풀이> BFS
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
숨바꼭질 문제에서 경로가 추가된 문제입니다.
parents 배열을 만들고 방문 체크를 하면서 cur -1, cur +1, 2 * cur의 부모를 cur로 만들고
cur == k가 되는 순간에 cur의 부모를 계속 따라가면서 배열에 저장하고 역순으로 출력하면 됩니다.
<C++ 소스 코드>
|
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
67
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
int n, k;
int visited[100001];
int dist[100001];
int parents[100001];
vector<int> res;
int bfs() {
queue<int> Q;
Q.push(n);
visited[n] = true;
dist[n] = 0;
parents[n] = n;
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
if (cur == k) {
int s = cur;
while (parents[s] != s) {
res.push_back(s);
s = parents[s];
}
res.push_back(s);
return dist[cur];
}
if (2 * cur <= 100000 && !visited[2 * cur]) {
Q.push(2 * cur);
visited[2 * cur] = true;
dist[2 * cur] = dist[cur] + 1;
parents[2 * cur] = cur;
}
if (cur - 1 >= 0 && !visited[cur - 1]) {
Q.push(cur - 1);
visited[cur - 1] = true;
dist[cur - 1] = dist[cur] + 1;
parents[cur - 1] = cur;
}
if (cur + 1 <= 100000 && !visited[cur + 1]) {
Q.push(cur + 1);
visited[cur + 1] = true;
dist[cur + 1] = dist[cur] + 1;
parents[cur + 1] = cur;
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
cout << bfs() <<'\n';
int len = res.size();
for (int i = len - 1; i >= 0; i--) {
cout << res[i] << " ";
}
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 17071번] 숨바꼭질 5 (0) | 2021.11.25 |
|---|---|
| [백준 12851번] 숨바꼭질2 (0) | 2021.11.22 |
| [백준 6593번] 상범 빌딩 (0) | 2021.11.19 |
| [백준 5014번] 스타트링크 (0) | 2021.11.19 |
| [백준 2146번] 다리 만들기 (0) | 2021.11.19 |