[백준/BOJ] 17071번 숨바꼭질 5 (C++)

www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

굉장히 난이도가 있는 BFS 문제, 일반적인 BFS 접근으로는 위의 문제를 해결할 수 없습니다...

문제를 해결하기 위한 포인트는 수빈이가 짝수초에 접근한 위치는 짝수초에 또 방문할 수 있고, 홀수초에 접근한 위치는 홀수초에 또 방문할 수 있다는 것입니다. 그러므로 현재 수빈이의 위치를 중심으로 시간이 지날 때 마다 몇초에 해당 위치를 최초로 방문하게 되는지 기록하고, 시간대가 짝수인지 홀수인지 구분하기 위해 2차원 visit배열을 사용하는 것입니다. 수빈이의 이동을 모두 확인했으면, 그 후 동생이 이동하면서 수빈이를 만날 수 있는지 확인하면 됩니다.

 

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 500000
using namespace std;

int n, k;
int visit[MAX + 1][2];

// 동생의 이동 거리 구하기
int getSum(int n) {
    return n * (n + 1) / 2;
}

// 수빈이의 이동 BFS : 짝수시간, 홀수시간의 첫 방문 시간을 기록
void moveOfSubin() {
    memset(visit, -1 ,sizeof(visit));
    queue<pair<int, int> > q;
    q.push({n, 0});
    
    while(!q.empty()) {
        int now = q.front().first;
        int time = q.front().second;
        q.pop();
        
        if(now < 0 || now > MAX) continue;
        if(visit[now][time % 2] != -1) continue;
        
        visit[now][time % 2] = time;
        q.push({now * 2, time + 1});
        q.push({now - 1, time + 1});
        q.push({now + 1, time + 1});
    }
}

// 동생의 이동
void moveOfSister() {
    for(int t = 0; t < MAX; t++) {
        int sister = k + getSum(t);
        if(sister > MAX) break;
        // 수빈이가 동생보다 먼저 도착했던 곳이거나 같이 도착한 경우
        if(visit[sister][t % 2] != -1 && visit[sister][t % 2] <= t) {
            cout<<t;
            return;
        }
    }
    // 동생의 이동이 500,000을 넘어 수빈이와 만나지 못한 경우
    cout<<"-1";
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    
    moveOfSubin();
    moveOfSister();
}