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

17071번: 숨바꼭질 5

---

 

문제)

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

 

 

입력 :

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

 

 

출력 :

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

 

 

풀이)

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int n, k;
// 이 문제는 수빈이와 동생의 홀짝 관계가 중요하다.
int visited[2][500004];
int turn = 1;
bool flag;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
 
    // 같은 위치에 있다면
    if (n == k)
    {
        cout << 0 << '\n';
        return 0;
    }
 
    // 수빈이가 예를 들어 10초에 x에 도달했다고 하자.
    // 그런데 동생이 20초에 x에 도착했다고 하면
    // 수빈이와 동생은 20초에 만날 수 있다.
    // 10초에 도착한 후 -1, +1을 반복하여 위치를 유지
    // -1, +1을 반복해야하기 때문에 홀짝이 중요하게 된다.
 
    // 특정 위치 x에 가장 빠르게 도달한 시간을 홀짝으로 나누어 생각한다.
    // - 수빈이가 10초에 x지점으로 최초 도달했다면 12, 14, 16,에도 x에 도달할 수 있다.
    // - 수빈이가 5초에 x지점에 최초 도달했다면 7, 9, 11,에도 x에 도달할 수 있다.
 
 
    // 동생이 계속해서 이동하므로, 
    // 동생의 위치에 집중 해야한다.
    queue<int> q;
    visited[0][n] = 1;
    q.push(n);
 
    while (!q.empty())
    {
        k += turn;
 
        if (k > 500000) break;
        if (visited[turn % 2][k])
        {
            flag = 1;
            break;
        }
 
        // 각 턴마다 이동 // 홀짝을 나누어서 계산하기 때문에
        // while(!q.empty())가 아닌 q_size를 만들어 계산한다.
        int q_size = q.size();
        for (int i = 0; i < q_size; i++)
        {
            int x = q.front();
            q.pop();
            for (auto nx : { x + 1, x - 1, x * 2 })
            {
                if (nx < 0 || nx > 500000) continue;
                if (visited[turn % 2][nx]) continue;
 
                visited[turn % 2][nx] = visited[(turn + 1) % 2][x] + 1;
                if (nx == k)
                {
                    flag = 1;
                    break;
                }
                q.push(nx);
            }
            if (flag) break;
        }
        if (flag) break;
        turn++;
    }
 
    if (flag)
    {
        cout << turn << '\n';
    }
    else
    {
        cout << -1 << '\n';
    }
 
    return 0;
}

 

 

---

출처 : https://www.acmicpc.net/problem/17071 

17071번: 숨바꼭질 5