[1697번] 숨바꼭질

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

BFS로 해결하면 되는 문제이다.

DP로 접근하기에는 갱신해야될 부분이 많이 있기에 BFS로 해결하되 visit배열을 두고 방문하였는지 체크하면 된다.

visit가 이미 true(1)인 상태일때 어느점에서 방문을 시도한다면 이미 최소 이동 횟수보다 더 많은 이동횟수로 오는것이기에

가장 빠르게 방문한 값에서 visit를 true로 바꿔주면 어떠한 변수도 없다.

이 문제 소스 코드를 기반으로 숨바꼭질 2, 숨바꼭질 3을 해결 할 수 있다.

소스 코드 : 

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

#include <cstdio> #include <iostream> #include <queue> #include <limits.h>   using namespace std;   #define MAX 100000   typedef pair<int, int> pii; queue <pii> q;   int visit[200001];   int main() {     int pos, target;     scanf("%d %d", &pos, &target);       q.push(pii(0, pos));       int ret = INT_MAX;     int cnt = 0;       if (pos == target)         printf("0");            else      {         while (!q.empty())          {             int x = q.front().second;             int cnt = q.front().first;               q.pop();             visit[x] = 1;               if (x == target)                 ret = min(ret, cnt);               if (x * 2 <= MAX && x * 2 >= 0 && visit[x * 2] == 0)                 q.push(pii(cnt + 1, x * 2));               if (x - 1 >= 0 && x - 1 <= MAX && visit[x - 1] == 0)                  q.push(pii(cnt + 1, x - 1));                          if (x + 1 <= MAX && x + 1 >= 0 && visit[x + 1] == 0)                  q.push(pii(cnt + 1, x + 1));                      }         printf("%d", ret);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus