[BOJ] 백준 13549 숨바꼭질 3

문제링크 : https://www.acmicpc.net/problem/13549


이 문제 역시 숨바꼭질 문제이고 BFS로 풀었다.
이전 문제는 어떤 시도마다 무조건 1초가 걸렸지만 이번 문제에서는
2배의 거리를 갈때는 0초가 걸린다는 것을 인지해야 한다.

소스코드 :

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

#include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; int n, k; int visited[200002]; int Calc(int num, int nx) {     if (num == 0) return nx - 1;     else if (num == 1) return nx + 1;     else return 2 * nx; } int main() {     cin >> n >> k;     fill_n(visited, 200002, -1);     //priority_queue<int> q;     queue<int> q;     q.push(n);     visited[n] = 0;     int second = 0;     while (!q.empty()) {         int qSize = q.size();         for (int s = 0; s < qSize; s++) {             int cur = q.front();             if (cur == k) {                 cout << visited[cur];                 while (!q.empty())q.pop();                 break;             }             q.pop();             for (int i = 0; i < 3; i++) {                 int val = Calc(i, cur);                 if (val < 200002 && visited[val] == -1) {                     q.push(val);                     visited[val] = (i == 2 ? visited[cur] : visited[cur] + 1);                     if (val == cur * 2) {                         visited[val] = visited[cur];                     }                 }             }         }         second++;     } } Colored by Color Scripter

cs