[BOJ]17071 숨바꼭질5

• 숨바꼭질 시리즈 최종본(hhhard)
• sol(시간초과)

#include <bits/stdc++.h>
using namespace std;
int N, K, cx, tx, level, nx;
int dx[2] = {-1, 1};
void bfs(){
    queue<tuple<int, int, int>> que;
    que.push({N, K, 1});
    while(!que.empty()){
        cx = get<0>(que.front());
        tx = get<1>(que.front());
        level = get<2>(que.front());
        if(tx >= 500001){
            cout << -1 << '\n';
            return;
        }
        if(cx == tx){
            cout << level - 1 << '\n';
            return;
        }
        que.pop();
        for(int i = 0; i < 3; ++i){
            if(i != 2) nx = cx + dx[i];
            else nx = 2 * cx;
            if(nx < 0 || nx >= 500001) continue;
            que.push({nx, tx + level, level + 1});
        }
    }
    cout << -1 << '\n';
    return;
}
int main(){
    cin >> N >> K;
    bfs();
    return 0;
}

• sol(정석)
• idea1: 언니가 짝수초에 방문한 위치는 짝수초에 다시 방문 가능(because +1, -1 이동)
• idea2: 언니가 홀수초에 방문한 위치는 홀수초에 다시 방문 가능(because +1, -1 이동)
• idea3: 언니가 정점 n에 있을 때 시간이 t라면 동생 위치 = k + t * (t + 1) / 2(등차수열)

1. 언니의 위치와 시간을 저장하는 큐 생성 & BFS 탐색 수행
2. 큐 pop 수행 시, t초 후 동생과 언니가 n에서 만나는지 확인
3. 방문 체크는 idea 1|2를 적용해 정점 n을 t초에 방문했다면, 짝수초 후에 다시 방문하는 점을 이용
4. t초일 때, 동생의 위치 n을 구해 언니가 위치 n을 짝수초에 방문 or 홀수초에 방문 체크

#include <bits/stdc++.h>
#define x first
#define t second
using namespace std;
int N, K;
bool visited[500001][2];
int bfs(){
    queue<pair<int, int>> que;
    que.push({N, 0});// 언니 위치 N, 현재 시간 0
    visited[N][0] = true;
    while(!que.empty()){
        auto cur = que.front();
        que.pop();
        // K + cur.t * (cur.t + 1) / 2: t초일 때, 동생의 위치
        //= 동생의 위치가 최대 범위를 넘어갈 경우 return -1
        if(K + cur.t * (cur.t + 1) / 2 >= 500001) return -1;
        //t초(짝수 or 홀수)일 때 동생의 위치가 이미 방문된 위치라면 return cur.t
        if(visited[K + cur.t * (cur.t + 1) / 2][cur.t % 2]) return cur.t;
        //현재 위치 * 2 도착지가 범위 내면서, 해당 지역을 같은 타임라인대에 방문하지 않은 경우
        if(2 * cur.x <= 500000 && !visited[2 * cur.x][(cur.t + 1) % 2]){
            //방문 처리
            visited[2 * cur.x][(cur.t + 1) % 2] = true;
            //다음 위치, 다음 시간대 넣기
            que.push({2 * cur.x, cur.t + 1});
        }
        //현재 위치 + 1 도착지가 범위 내면서, 해당 지역을 같은 타임라인대에 방문하지 않은 경우
        if(cur.x + 1 <= 500000 && !visited[cur.x + 1][(cur.t + 1) % 2]){
            //방문 처리
            visited[cur.x + 1][(cur.t + 1) % 2] = true;
            //다음 위치, 다음 시간대 넣기
            que.push({cur.x + 1, cur.t + 1});
        }
        //현재 위치 - 1 도착지가 범위 내면서, 해당 지역을 같은 타임라인대에 방문하지 않은 경우
        if(cur.x - 1 >= 0 && !visited[cur.x - 1][(cur.t + 1) % 2]){
            //방문 처리
            visited[cur.x - 1][(cur.t + 1) % 2] = true;
            //다음 위치, 다음 시간대 넣기
            que.push({cur.x - 1, cur.t + 1});
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K;
    cout << bfs();
    return 0;
}