[13913번] 숨바꼭질 4

문제 출처 :

https://www.acmicpc.net/problem/13913

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. BFS

[13549번] 숨바꼭질 3 :: http://www.crocus.co.kr/627

[12851번] 숨바꼭질 2 :: http://www.crocus.co.kr/628

[1697번] 숨바꼭질 :: http://www.crocus.co.kr/629

이 세문제를 미리 풀어본 후 풀어보면 더 좋은 문제로 접할 수 있을 듯 하다.

이 문제는 숨바꼭질 문제에 자취를 요구하는 문제이다.

즉, 이동해왔던 자취를 알아야 하고, 그 자취를 어떻게 표현해 볼 것인가 요구하는 문제인데

소스 코드는 [1697번] 숨바꼭질 문제와 매우 유사하다.

한가지 달라진 점은 trace배열에 이전에는 0 아니면 1로 설정하여 방문정도만 체크했지만

이번에는 방문할 위치에 현재 방문하고있는 위치를 저장시키며 진행하면 된다는 것이 차이가 난다.

그리고 이 문제는 항상 cost가 1씩 증가하고 있고, 큐에서는 cost가 증가하는 순서대로 pop이되며

탐색하는 방식임을 명심하고 있어야 한다.(결국 break전 마지막 cost가 최단 거리임을 알 수 있기 때문이다.)

소스 코드 : 

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

#include <cstdio> #include <iostream> #include <vector> #include <queue> #include <memory.h>   #define MAX 100005   using namespace std;   // cost, pos queue<pair<int, int>> q;   int trace[MAX];   int main() {     int start, finish;     int ans;       vector<int> vc;       scanf("%d %d", &start, &finish);       memset(trace, -1, sizeof(trace));       q.push(make_pair(0, start));       while (!q.empty())     {         int cost = q.front().first;         int here = q.front().second;           q.pop();           // 현재 위치가 도착점에 도달했을 때         if (here == finish)         {             // 지금까지 수행 횟수를 ans에 저장             // (결국 몇번만에 갔는지 의미)             ans = cost;             break;         }           // 이 위치를 아직 와본적이 없다면         // 큐에 넣어주고 다음 위치에 이전 위치의 자취를 남긴다.         if (here * 2 <= MAX && trace[here * 2] == -1)         {             q.push(make_pair((cost + 1), here * 2));             trace[here * 2] = here;         }           if (here + 1 <= MAX && trace[here + 1] == -1)         {             q.push(make_pair((cost + 1), here + 1));             trace[here + 1] = here;         }           if (here - 1 >= 0 && trace[here - 1] == -1)         {             q.push(make_pair((cost + 1), here - 1));             trace[here - 1] = here;         }     }       printf("%d\n", ans);       // 끝점부터 시작점까지 갈 때 까지 vector에 push한다.     int pos = finish;     while (pos != start)     {         vc.push_back(trace[pos]);         pos = trace[pos];     }       // 역순 출력(스택 방식)     for (int i = vc.size() - 1; i >= 0; i--)         printf("%d ", vc[i]);       printf("%d", finish);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus