1697 숨바꼭질

이건 어떻게 풀어야 할지 몰라서 고민했다. 

처음에 DP로 풀어보려다가 식이 안 나오고 어려워서 다른사람 풀이를 참고했다.

이야... 큐로 넣어서 bfs로 풀더라...

그래프 처럼 안 생겼는데 이걸 bfs로 생각해서 풀다니 신기하다.

 

-1, +1, *2한 계산 결과를 큐에 넣고 큐에서 하나씩 빼가면서 동생의 위치랑 일치하는지 비교한다. 

이 다음 궁금한게 이렇게 하면 최소 횟수가 되나? 싶었다. 

그래프로 그려보면 높이가 움직인 횟수이고 bfs는 너비 우선 탐색이라 처음 일치한 게 최소라는 게 보장된다!

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


bool visited[100005];
queue<ii> q;

bool valid(int n) {
    if (n < 0 || n > 100000 || visited[n])
        return false;
    return true;
}

int bfs(int k) {
    while(!q.empty())
    {
        int data = q.front().xx;
        int depth = q.front().yy;
        q.pop();
        
        if (data == k)
            return depth;
        
        if (valid(data - 1)) {
            q.push({data - 1, depth + 1});
            visited[data - 1] = true;
        }
        if (valid(data + 1)) {
            q.push({data + 1, depth + 1});
            visited[data + 1] = true;
        }
        if (valid(data * 2)) {
            q.push({data * 2, depth + 1});
            visited[data * 2] = true;
        }
    }
    return 0;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    q.push({n, 0});
    visited[n] = true;
    cout << bfs(k);
    
    
    return 0;
}