[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질1)

포인트

1. BFS (너비 우선 탐색)

2. 기본적인 것들은 똑같고 조건들만 다름을 이해하자

#include<iostream>
#include<queue>

using namespace std;
#define MAX 100001
bool visited[MAX];
int n, m;

int bfs() {
    queue<int> q;
    int time = 0;
    q.push(n);

    while (1) {
        int size = q.size();

        for (int i = 0; i < size; i++) { // 한턴마다 시간을 구하기 위해서 이다.
            n = q.front();
            q.pop();
            if (n == m) return time;

            if (n > 0 && !visited[n - 1]) { //범위체크 && 방문하지 않았거나
                q.push(n - 1);
                visited[n - 1] = 1;
            }
            if (n < 100000 && !visited[n + 1]) { //범위체크 && 방문하지 않았거나
                q.push(n + 1);
                visited[n + 1] = 1;
            }
            if (n * 2 <= 100000 && !visited[n * 2]) { //범위체크 && 방문하지 않았거나
                q.push(n * 2);
                visited[n * 2] = 1;
            }
        }
        time++; // 한턴이 끝났음으로 시간을 늘려준다.
    }
}

int main() {
    cin >> n >> m;
    cout << bfs();
    return 0;
}