숨바꼭질 5

백준 17071번: 숨바꼭질 5

아이디어

동생이 도망간다. 숨바꼭질 1~5중에 가장 어렵다. 한번 방문한 위치에 표시하고 이후에 방문하지 않는 방법을 사용하면, 동생이 나중에 거기를 방문히고, 수빈이가 앞으로 갔다 다시 뒤로 와서 만나는 경우를 찾아낼 수 없다. 그렇다고 방문한 위치를 표시하지 않으면 시간초과다. 어떻게 하면 좋을까?
수빈이가 먼저 도달한 곳에 동생이 몇 초 후에 도달한 경우 수빈이가 왕복 1회 즉 2초동안 기다려주면 만날 수 있다. 예를 들어 수빈이가 n초에 도달한 곳에 동생이 n+2, n+4, n+6초에 도달한 경우 둘이 만날 수 있다는 뜻이다.
수빈이와 동생이 둘 다 짝수 초에 도달한 경우와 홀수 초에 도달한 경우를 나눠서 생각하면 문제를 풀 수 있을 것이다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, K;
int visited[2][500001]; // even, odd

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    queue<vector<int>> q;
    int n, k, t;
    int ans = INT_MAX;
    cin >> N >> K;
    visited[0][N] = 1;
    q.push({N, K, 0});
    while (!q.empty()) {
        n = q.front()[0];
        k = q.front()[1];
        t = q.front()[2];
        if (n == k){
            ans = min(ans, t);
        }
        if (k > 500000) {
            break;
        }
        
        if (visited[t%2][k]) {
            ans = min(ans, t);
        }
        
        q.pop();

        if (n+1 <= 500000 && !visited[(t+1)%2][n+1]) {
            visited[(t+1)%2][n+1] = visited[t%2][n] + 1;
            q.push({n+1, k+t+1, t+1});
        }
        if (n-1 >= 0 && !visited[(t+1)%2][n-1]) {
            visited[(t+1)%2][n-1] = visited[t%2][n] + 1;
            q.push({n-1, k+t+1, t+1});
        }
        if (n*2 <= 500000 && !visited[(t+1)%2][n*2]) {
            visited[(t+1)%2][n*2] = visited[t%2][n] + 1;
            q.push({n*2, k+t+1, t+1});
        }
    }
    
    if (ans == INT_MAX) cout << -1;
    else cout << ans;
    
    return 0;
}

여담

숨바꼭질 올클 ㄷㄷ vector 말고 tuple을 사용했으면 시간 더 짧았을듯?