문제
https://www.acmicpc.net/problem/13913
문제해설
수빈이가 있는 위치 n에서부터 +1, -1, *2 만큼씩 움직여
동생이 있는 k지점까지 최소 시간으로 이동했을 때
걸리는 시간과 경로를 출력하면 된다.
문제풀이
BFS를 이용해서 풀었다.
처음에는 잘못 생각해서 우선순위 큐를 쓰고 했었는데
생각해보니 bfs는 가장 먼저 도착한게 가장 최단거리이다.
그냥 bfs처럼 짜면 된다.
조금 까다롭다고 느낄 수 있는 부분이
마지막에 경로를 출력하는 부분이다. 이 부분은 방문을 확인하는 배열에서
다음으로 가야할 곳에 현재 번호를 입력해두었다.
print함수에서 stack에 역으로 쌓아서
순서대로 출력될 수 있게 만들어 주었다.
마지막으로 이 문제를 틀렸던 이유는
0에서 시작하는 경우에 문제가 되었다.
방문배열이 0일 경우에 방문하지 않은 것으로 판단하기 때문이다.
그래서 시작점을 -11로 두고
0에서 시작한 경우는 다음으로 방문하는 곳에 -1을 넣어두었다.
전체코드
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
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>P;
int n, k;
queue<P>q;
int visited[200001];
int dx[] = { 1,-1,2 };
void print(int cnt) {
cout << cnt << "\n";
stack<int>res;
for (int i = k; ; i = visited[i]) {
res.push(i);
if (visited[i] == -1) {
res.push(0);
break;
}
if (visited[i] == -11)
break;
}
while (!res.empty()) {
cout << res.top() << " ";
res.pop();
}
}
void bfs() {
while (!q.empty()) {
int now = q.front().first;
int cnt = q.front().second;
q.pop();
if (now == k)
print(cnt);
for (int i = 0; i < 3; i++) {
int next;
if (i == 2)
next = now * 2;
else
next = now + dx[i];
if (next < 0 || next > 200000)
continue;
if (visited[next])
continue;
if (now == 0)
visited[next] = -1;
else
visited[next] = now;
q.push({ next, cnt + 1 });
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
q.push({ n,0 });
visited[n] = -11;
bfs();
return 0;
}