문제
풀이
단순 BFS의 경로 역추적 문제이다. Before 함수를 통해 그 전 경로들을 계속 저장해나가는 방식으로 풀이하였다. Reference 코드를 첨부한다.
소스 코드
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 100000 + 1;
int parent[MAX]; //해당 지점 방문 직전 지점 저장
bool visited[MAX];
vector<int> path; //경로 저장
int minSecond(int N, int K)
{
queue<pair<int, int>> q;
q.push(make_pair(N, 0));
visited[N] = true;
while (!q.empty())
{
int curLoc = q.front().first;
int curSec = q.front().second;
q.pop();
if (curLoc == K) //목적지 도달 시 break
{
int idx = curLoc;
//그전에 방문했던 지점을 거슬러 올라간다
while (idx != N)
{
path.push_back(idx);
idx = parent[idx];
}
path.push_back(N);
return curSec;
}
//세 가지 경우의 수
//이미 방문한 지점은 큐에 넣지 않는다
//자료구조 시간에 배운 disjoint set 이용
if (curLoc + 1 < MAX && !visited[curLoc + 1])
{
q.push(make_pair(curLoc + 1, curSec + 1));
visited[curLoc + 1] = true;
parent[curLoc + 1] = curLoc;
}
if (curLoc - 1 >= 0 && !visited[curLoc - 1])
{
q.push(make_pair(curLoc - 1, curSec + 1));
visited[curLoc - 1] = true;
parent[curLoc - 1] = curLoc;
}
if (curLoc * 2 < MAX && !visited[curLoc * 2])
{
q.push(make_pair(curLoc * 2, curSec + 1));
visited[curLoc * 2] = true;
parent[curLoc * 2] = curLoc;
}
}
}
int main(void)
{
int N, K;
cin >> N >> K;
cout << minSecond(N, K) << "\n";
//거꾸로 저장되어있으므로
for (int i = path.size() - 1; i >= 0; i--)
cout << path[i] << " ";
cout << endl;
return 0;
}
//출처: https://jaimemin.tistory.com/584 [꾸준함]
