[백준] 1697 숨바꼭질

수빈아와 동생의 숨바꼭질이다

내가 찾아드림

수빈이는 N에 있고 동생은 K에 있다

수빈이의 이동 가능한 경로는

1) N+1

2) N-1

3) N*2

그럼 이 3가지 경우를 BFS를 통해 동생을 찾으면 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, k;
int dist[100010];
bool check[100010];
 
int main() {
    scanf("%d %d", &n, &k);
    queue<int> q;
    q.push(n);
    dist[n] = 0;
    check[n] = true;
    while (!q.empty()) {
        int here = q.front();
        q.pop();
 
        int next = here - 1;
        if (next >= 0 && !check[next]) {
            check[next] = true;
            dist[next] = dist[here] + 1;
            q.push(next);
        }
        
        next = here + 1;
        if (next <= 100000 && !check[next]) {
            check[next] = true;
            dist[next] = dist[here] + 1;
            q.push(next);
        }
 
        next = here * 2;
        if (next <= 100000 && !check[next]) {
            check[next] = true;
            dist[next] = dist[here] + 1;
            q.push(next);
        }
    }
    printf("%d\n", dist[k]);
}