문제

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 100001

// 숨바꼭질

queue<pair<int, int> > q;
bool visited[MAX] = {false, };
int N, K;

int bfs(int n) {
    q.push(make_pair(n, 0));

    visited[n] = true;

    while(!q.empty()) {
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if(x == K) { return cnt; }

        if(x+1<MAX && visited[x+1]==false) {
            q.push(make_pair(x+1, cnt+1));
            visited[x+1] = true;
        }
        // 주의) 빼기니까 0보다 클 때를 검사할 것
        if(x-1>=0&& visited[x-1]==false) {
            q.push(make_pair(x-1, cnt+1));
            visited[x-1] = true;
        }
        if(x*2<MAX && visited[x*2]==false) {
            q.push(make_pair(x*2, cnt+1));
            visited[2*x] = true;
        }

    }

    return 0;
}

int main() {
    ios::sync_with_stdio(0);

    cin >> N >> K;

    cout << bfs(N) << '\n';



    return 0;
}

📌

이 문제는 1차원 BFS지만 다른 BFS 문제처럼 큐를 선언하고 방문 여부를 저장할 배열(1차원)을 만든다.
출발 지점을 함수의 파라미터로 받으며 큐에 넣고 큐가 빌 때까지 x+1, x-1, x*2 계산을 하며 범위를 벗어나지 않으며 방문하지 않았는지 여부를 탐색하며 큐의 second에 방문 횟수를 저장시킨다.

원하는 자리에 도달했을 때 총 방문 횟수를 리턴해주면 된다.