[백준 17071번] 숨바꼭질 5

문제 링크: https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

<문제 풀이> BFS

수빈이가 정점 n에 있을 때 시간을 t라고 하면 동생의 위치는 (등차수열의 합 공식을 사용해서 구하면)

k + t*(t+1)/2에 있습니다.

 

수빈이의 위치와 시간을 저장하는 큐를 만들고 BFS를 돌리고

큐에서 pop을 할 때  t초 후 동생과 수빈이가 n에서 만나는지를 확인하면 됩니다.

 

그런데 n 제한이 50만이기 때문에 여기서 모든 정점을 큐에 넣으면 시간 초과, 메모리 초과가 나게 됩니다.

적절하게 방문 체크를 해서 이미 큐에 넣은 정점은 큐에 다시 넣지 않게 해야 됩니다.

 

문제의 입력을 트리 형태로 그려보면 수빈이가 정점 n을 t초에 방문했을 때 짝수 초 후에 그 정점을 다시 방문할 수 있다는 것을 알 수 있습니다. 

(-1 -> +1 하면 제자리)

 

그러면 BFS를 진행하면 정점 n일 때 레벨 t을 알 수 있으니깐 t초 일 때 동생의 위치 n을 구해서

수빈이가 위치 n을 짝수 초에 방문했는지, 홀수 초에 방문했는지를 visited 배열로 체크하면 됩니다.

(만약 수빈이가 홀수 초에만 n에 방문하고 동생이 짝수 초에만 n에 방문하면 서로 만날 수 없음)

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int n, k; 
bool visited[500001][2];
 
int bfs() {
    queue<pair<int, int> > Q;
    Q.push({ n, 0 });
    visited[n][0] = true;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (k + cur.Y * (cur.Y + 1) / 2 > 500000) {
            return -1;
        }
        if (visited[k + cur.Y * (cur.Y + 1) / 2][cur.Y % 2]) {
            return cur.Y;
        }
        if (2 * cur.X <= 500000 && !visited[2 * cur.X][(cur.Y + 1) % 2]) {
            Q.push({2 * cur.X, cur.Y + 1 });
            visited[2 * cur.X][(cur.Y + 1) % 2] = cur.Y + 1;
        }
        if (cur.X + 1 <= 500000 && !visited[cur.X + 1][(cur.Y + 1) % 2]) {
            Q.push({cur.X + 1, cur.Y + 1 });
            visited[cur.X + 1][(cur.Y + 1) % 2] = cur.Y + 1;
        }
        if (cur.X - 1 >= 0 && !visited[cur.X - 1][(cur.Y + 1) % 2]) {
            Q.push({cur.X - 1, cur.Y + 1 });
            visited[cur.X - 1][(cur.Y + 1) % 2] = cur.Y + 1;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    cout << bfs();
    return 0;
}