백준 9663:숨바꼭질

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

백준 9663번 숨바꼭질 문제입니다. 이번 문제도 BFS 알고리즘을 사용해서 풀었어요. DFS로 해결하려면 힘들 것 같아요. 만약 testCase가 50000 1일 경우에 정말 많은 스택공간이 필요하기 때문에 재귀함수는 메모리초과가 날 것 같고, 스택을 이용하면 시간초과가 날것 같기에.. BFS를 활용하는게 좋아보아요. 처음 구현할 때, 1에서 출발하면 *2 나 +1이 중복되서 체크하는 데 문제가 있을거라고 생각했었는데, 어차피 둘다 이동 횟수는 1증가해서 상관 없을 것 같네요..

밑에는 제 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> visited;  //방문체크와 동시에 횟수 측정
int BIG;
bool isSafe(int pos) {  //범위 체크
    if (pos<0 || pos > BIG + 1) return false;
    else return true;
}
 
int main(void) {
    int N, K;
    cin >> N >> K;
    BIG = K > N ? K : N;  //큰 수를 찾아요
    queue<int> q;
    q.push(N); visited.resize(BIG + 2);  //큰 수 만큼 배열을 만들어요
    visited[N] = 1;
    while (!q.empty()) {
        int cur = q.front();
        if (cur == K) break;  //목적지 까지 도착하면 break;
        if (isSafe(cur * 2) && !visited[cur * 2] && cur < K) {//방문가능,방문하지 않았다면
            visited[cur * 2] = visited[cur] + 1;  //방문체크 후
            q.push(cur * 2);  //큐에 삽입
        }
        if (isSafe(cur-1) && !visited[cur - 1]) {  //방문가능,방문하지 않았다면
            visited[cur - 1] = visited[cur] + 1;  //방문체크 후
            q.push(cur - 1);  //큐에 삽입
        }
        if (isSafe(cur + 1) && !visited[cur + 1] && cur < K) {  //방문가능,방문하지 않았다면
            visited[cur + 1] = visited[cur] + 1;  //방문체크 후
            q.push(cur + 1);  //큐에 삽입
        }
        
        q.pop();
    }
    cout << visited[K] - 1 << endl;
 
    return 0;
}