숨바꼭질 5

일단 이문제 개어렵다...

일반적인 BFS로는 못 푼다.

수빈이는 -1, +1로 왔다리 갔다리 할 수 있다는 부분을 알아야한다.

그래서 x라는 좌표에 수빈이가 2초에 왔다면은 동생은 2초든 4초든 6초에 x에 오면 무조건 만날 수 있다.

반대로 3초에 x좌표에 수빈이가 왔다면은 동생은 3초 5초 7초..이런식으로 오면은 만날 수 있다.

turn으로 짝수초의 턴인지 홀수초의 turn인지를 나누어서 방문하다가 동생이 방문한? 할 곳인지 확인을 해준다.

cpp 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 1000004

const int max_n = 500000;
int visited[2][max_n + 4], a, b, ok, turn = 1;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> a >> b;
    if (a == b)
    {
        cout << 0 << endl;
        return 0;
    }

    queue<int> q;
    visited[0][a] = 1;
    q.push(a);
    while (!q.empty())
    {
        b += turn;
        if (b > max_n) break;
        if (visited[turn % 2][b])
        {
            ok = true;
            break;
        }
        int qSize = q.size();
        for (int i = 0; i < qSize; ++i)
        {
            int x = q.front(); q.pop();
            for (int nx : {x - 1, x + 1, x * 2})
            {
                if (nx < 0 || nx  > max_n || visited[turn % 2][nx] ) continue;
                visited[turn % 2][nx] = visited[(turn + 1) % 2][x] + 1;
                if (nx == b)
                {
                    ok = 1;
                    break;
                }
                q.push(nx);
            }
        }
        if (ok) break;
        ++turn;
    }

    if (ok) cout << turn << endl;
    else cout << -1 << endl;

    return 0;
}