<SW>/알고리즘 + 자료구조
[BFS] 숨바꼭질 4
Hading
2018. 10. 16. 16:35
728x90
문제링크 : https://www.acmicpc.net/problem/13913
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 | #include<iostream> #include<queue> #include<vector> using namespace std; int n, k; int visit[100001]= { 0 }; int route[100001]={ -1, }; vector<int> path; //경로 저장 int bfs(int start) { queue<int> q; q.push(start); visit[start] = 1; while (!q.empty()) { int x = q.front(); q.pop(); if (x == k) { int idx = x; while (idx != n) { path.push_back(idx); idx = route[idx]; } path.push_back(n); return visit[x] - 1; } if (x + 1 <= 100000 && visit[x + 1] == false) { visit[x + 1] = visit[x] + 1; route[x + 1] = x; q.push(x + 1); } if (x-1 >= 0 && x - 1 <= 100000 && visit[x - 1] == false) { visit[x - 1] = visit[x] + 1; route[x - 1] = x; q.push(x - 1); } if (x * 2 <= 100000 && visit[x * 2] == false) { visit[x *2] = visit[x] + 1; route[x *2] = x; q.push(x *2); } } } int main() { cin >> n >> k; cout << bfs(n)<<endl; for (int i = 0; i <= 2 * k; i++) { cout << route[i]<<" "; } cout << endl; //거꾸로 저장되어있으므로 for (int i = path.size() - 1; i >= 0; i--) cout << path[i] << " "; cout << endl; return 0; } | cs |
728x90