백준 17071 숨바꼭질5 풀이(c++)

문제 링크

성능 요약

메모리: 6060 KB, 시간: 16 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 27일 10:50:19

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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>
#include <vector>
#include <cstring> 

using namespace std;

int N, K;
int visited[500001][2];  

int bfs()
{
    queue<pair<int, int>> q; 
    q.push({ N, 0 });
    visited[N][0] = 1;

    while (!q.empty()) 
    {
        int iNow = q.front().first;
        int iTime = q.front().second;
        q.pop();

        int brother = K + iTime * (iTime + 1) / 2;
        if (brother > 500000) 
            return -1; 

        if (visited[brother][iTime % 2]) 
            return iTime;

        for (int next : {iNow + 1, iNow - 1, iNow * 2})
        {
            if (next >= 0 && next <= 500000 && !visited[next][(iTime + 1) % 2]) 
            {
                visited[next][(iTime + 1) % 2] = 1;
                q.push({ next, iTime + 1 });
            }
        }
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    memset(visited, 0, sizeof(visited)); 

    if (N == K) {
        cout << "0\n";
        return 0;
    }

    cout << bfs() << "\n";
    return 0;
}

 

단순한 bfs로 풀다가 한참 못풀었다. 정점을 다시 재방문 하는 경우까지 생각해야해서 여러 방법을 사용하다 홀수와 짝수 별로 방문여부를 저장해두다가 목표에 닿으면 해당 타임을 아웃 하는식으로 해결했다.