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

1. 문제 출처

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

17071번: 숨바꼭질 5

 

 

 

 

2. 문제 접근

• 도착점이 고정되어 있는 일반적인 BFS문제와는 달리, 도착점도 동시에 이동하는 BFS문제
• 수빈이가 이동할 수 있는 경우는 다음 3가지밖에 없다.
  • 현재 위치 x에서 1칸 좌측(x - 1)으로 이동
  • 현재 위치 x에서 1칸 우측(x + 1)으로 이동
  • 현재 위치 x에서 순간이동하여 2배 떨어진 위치(x * 2)로 이동
• 특정 위치 x에 가장 빠르게 도달한 시간에 t라면, t+2, t+4, t+6, ... 초 후에도 x에 도달할 수 있다.
• 특정 위치 x에 가장 빠르게 도달한 시간을 짝수, 홀수인 경우로 나누어서 생각한다.
  • 수빈이가 10초에 x지점으로 최초 도달하였다면 12초, 14초,.. 일 때도 x지점으로 도달할 수 있다.
  • 수빈이가 5초에 x지점으로 최초 도달하였다면, 7초, 9초, 11초,... 일 때도 x지점으로 도달할 수 있다.
• 따라서, 동생이 홀수 초에 x지점에 도달을 했고, 수빈이가 이전 홀수 초에 이미 x지점을 방문했다는 것은 다시 동생이 도착한 시점에도 다시 x지점에 도달할 수 있음을 의미한다.

 

 

 

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int subin, brother;
bool visited[2][500001];

int getPos(int pos, int opt) {
    if (opt == 0) return pos - 1;
    else if (opt == 1) return pos + 1;
    else return pos * 2;
}


int bfs() {
    queue<pair<int, int>> q; // {수빈이의 현재 위치, 지난 시간}
    q.push({subin, 0});
    
    memset(visited, false, sizeof(visited));
    visited[0][subin] = true;

    while(!q.empty()) {
        
        int here = q.front().first;
        int sec = q.front().second;
        q.pop();

        // sec초가 지난 동생의 현재 위치
        int brotherPos = brother + sec * (sec + 1) / 2;

        // 동생이 이기는 경우: 수빈이가 도달하지 못하고 500,000을 넘어갔을 때
        if (brotherPos > 500000) return -1;

        // 수빈이가 동생을 잡는 경우
        if (visited[sec % 2][brotherPos]) return sec;
  
        ++sec;
        for (int opt = 0; opt < 3; ++opt) {
            int nextPos = getPos(here, opt);
            if (nextPos < 0 || nextPos > 500000) continue;
            if (visited[sec % 2][nextPos]) continue;
            visited[sec % 2][nextPos] = true;
            q.push({nextPos, sec});
        }
    } 

    return -1;
}

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

    cin >> subin >> brother;

    cout << bfs() << "\n";

    return 0;
}