[코테] 백준 - 숨바꼭질 5(17071)

문제

• 수빈이와 동생의 출발 지점 제공 (N, K)
• 수빈이는 이동 선택지가 3가지(+1, -1, *2)
• 동생은 이동 선택지가 1가지(매초 전에 이동한 거리의 +1만큼 이동)
• 수빈이와 동생이 만날 수 있는 가장 빠른 시간을 구할 것

풀이

• 완전탐색 문제로 분류
• BFS를 이용하여 수빈이와 동생의 위치를 추적하면 될것으로 추정
  ㅡ> 결과적으로 실패 및 시간 초과
• 동생의 이동 거리는 등차수열이므로 시간만 특정되면 계산 가능
• 수빈이의 경우만 -1의 선택지를 통해 뒤로 돌아올 수 있음
• 더불어 +1도 있으므로 2초마다 같은 자리에 있는 것도 가능
• 수빈이의 이동 거리와 시간이 중요
  ㅡ> 시간을 알면 동생의 이동 거리는 특정 가능하므로
• 결과적으로 수빈이는 3가지 선택지에 의해 짝수 초, 홀수 초마다 갈 수 있는 칸이 다름
  ㅡ> 짝/홀로 나누어 방문체크
• 시간을 1초씩 증가시키며 탐색 가능한 모든 노드 탐색
• 짝/홀로 방문체크하면서 시간 기준으로 탐색하지 않은 노드 탐색
• 시간을 기준으로 동생의 위치를 계산 ㅡ> 해당 위치를 짝/홀 방문체크 배열에서 확인
• 짝/홀 방문체크 배열의 값이 true라면 수빈이는 해당 지점을 돌아올 수 있으니 둘이 만난 것으로 판단 가능
  ㅡ> 시간 출력 및 종료

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAX=500001;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    
    vector<vector<bool>> visited(2,vector<bool>(MAX,false));
    queue<int> q;
    q.push(n);
    visited[0][n] = true;
    int time=0;
    while (!q.empty())
    {
        int brother=k+time*(time+1)/2;
        if (brother>=MAX) break;
        if (visited[time%2][brother])
        {
            cout<<time<<"\n";
            return 0;
        }
        int size=q.size();
        time++;
        for (int i=0;i<size;i++)
        {
            int cur=q.front();
            q.pop();
            for (int next:{cur-1,cur+1,cur*2})
            {
                if (next>=0&&next<MAX&&!visited[time%2][next])
                {
                    visited[time%2][next]=true;
                    q.push(next);
                }
            }
        }
    }
    
    cout << "-1\n"; // 따라잡을 수 없는 경우
    return 0;
}

 

---

참고자료

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