문제 URL : https://www.acmicpc.net/problem/13913
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
문제 접근법 :
n -> k로 이동 방법이 -1, 1 , *2 를 해서 k를 만드는문제고 어떻게 만드는지까지 출력하는 문제입니다.
n->k까지 만드는데 얼마만큼의 깊이를 탐색하는건 bfs면 충분합니다.
하지만 어떻게 만드는지 만들기위해 check[]를 true ,false만 이용한다면 어떻게 만드는지까지 만들기가 힘듭니다.
그렇다면 n에서 k까지 만드는데 -1,1, *2를 했으니 그했던과정을 check[]에서 어떻게 만들었는지 표시를 한수
반대로 k에서 n까지 만드는것을 반대로 1,-1, 나누기2 를해주면 됩니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
int n, k;
int check[200001];
int dir[4] = { 0,-1,1,2 };
void input() {
cin >> n >> k;
}
bool isrange(int t) {
return 0 <= t && t <= 200000;
}
int bfs() {
queue<int> q;
q.push(n);
check[n] = -1;
int cnt = 0;
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
int cur = q.front();
q.pop();
if (cur == k)
return cnt;
for (int i = 1; i <= 3; i++) {
int next = (i == 3 ? cur * dir[i] : cur + dir[i]);
if (isrange(next) && check[next] == 0) {
check[next] = i;
q.push(next);
}
}
}
cnt++;
}
return -1;
}
void solve() {
cout << bfs() << "\n";
vector<int> v;
int cur = k;
while (check[cur] != -1) {
v.push_back(cur);
cur = (check[cur] == 3 ? cur / dir[check[cur]] : cur - dir[check[cur]]);
}
v.push_back(cur);
for (int i = v.size() - 1; i >= 0; i--)
cout << v[i] << " ";
cout << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 7453 합이 0인 네 정수 (0) | 2022.03.07 |
|---|---|
| 백준 17436 소수의 배수 (0) | 2022.01.27 |
| 백준 3649 로봇 프로젝트 (0) | 2021.12.16 |
| 백준 18808 스티커 붙이기 (0) | 2021.12.15 |
| 백준 11967 불켜기 (0) | 2021.12.15 |
