숨바꼭질 5( BOJ 17071 )

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

17071번: 숨바꼭질 5

 

문제 파악하기

수빈이가 동생을 찾는데 걸리는 최소 시간을 구하는 문제입니다. 동생은 매초 1만큼 가속을 받아 이동하며, 수빈이는 현재 위치에서 ±1 또는 x2 만큼 이동할 수 있습니다. 이 문제에서 중요한 점은 수빈이가 항상 최선의 동선으로만 이동하지 않는다는 것입니다. 예를 들어, 수빈이가 17에 있으며 동생이 5에 있다고 가정해봅시다. 이 경우, 수빈이는 총 4번을 [ 17 > 18 > 17 > 16 > 15 ]의 동선으로 이동하면 동생을 찾을 수 있으며 이보다 빠르게 동생을 찾을 수는 없습니다. 이처럼 한 위치를 중복해서 이동하는 경우도 있기 때문에 단순히 한번 방문한 위치를 체크하고 탐색에서 배제할 수 없습니다. 그렇다고 모든 경우를 탐색하는 건 3^N만큼 가짓수가 증가하기에 시간 및 메모리 측면에서 불가능합니다. 그럼 어떤 방법을 사용할 수 있을까요?

 

문제 해결하기

우리가 주목할 점은 특정 위치에 동생이 도달하는 시간입니다. 만약 동생이 수빈이보다 먼저 특정 위치 X에 도착한다면 수빈이는 무슨 방법을 쓰더라도 X 위치에서는 동생을 찾을 수 없습니다. 하지만 수빈이가 동생보다 먼저 X 위치에 도달한다면 수빈이는 동생을 찾을 수도 있습니다. 수빈이가 먼저 도착한 다음, 앞뒤로 움직이면서 동생을 기다리면 되기 때문입니다. 하지만 모든 경우에 동생을 찾을 수 있는 건 아닙니다. 앞뒤로 움직인다는 건 2만큼의 시간이 필요하며, 동생이 X위치에 오는 시간과 타이밍이 맞지 않으면 서로 엇갈리게 됩니다. 그렇기에 X위치에서 동생과 수빈이의 도착 타이밍이 맞는지 맞지 않는지를 판단할 필요가 있습니다.

 

그럼 어떻게 해야 타이밍을 확인할 수 있을까요? 우린 여기서 2씩 증가한다는 점에 초점을 맞춰야 합니다. 2씩 증가한다는 의미는 곧 짝수 시간에 도착했으면 수빈이는 항상 짝수 시간에 X 위치에 도착할 수 있으며, 홀수 시간에 도착했으면 수빈이는 항상 홀수 시간에 도착할 수 있습니다. 따라서, 우리는 수빈이가 해당 위치에 도착하는 시간이 짝수/홀수 인지 확인하면 동생을 찾을 수 있는지 없는지 알 수 있습니다.

 

여기까지 구했으면 대략적인 알고리즘을 설계할 수 있습니다. 우선, 동생이 이동하는 위치를 먼저 기록합니다. 그리고 수빈이가 출발 지점부터 시작해서 갈 수 있는 모든 위치를 탐색하되, 도착하는 시간의 홀/짝 여부에 따라 탐색을 진행하면 됩니다. 만약 동생이 이동하는 위치에 도달하게 되면 2가지를 파악하면 됩니다. 첫 번째, 동생이 먼저 도착하는지 여부입니다. 만약 동생이 먼저 도착한다면 해당 위치에서는 동생을 찾을 수 없습니다. 두 번째, 동생이 도착하는 시간의 홀/짝 입니다. 만약 동생이 도착하는 시간과 수빈이가 도착하는 시간의 홀/짝 여부가 같다면 동생을 찾을 수 있지만 서로 다른 경우에는 찾을 수 없습니다. 기본적인 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <queue>
#include <utility>
#include <algorithm>
#define NMAX 500000
#define PAIR pair<int, int>
using namespace std;
 
int N, K;
 
int cur, curK, x, ret;
int pos[NMAX+10], check[NMAX+10][2];
queue< PAIR > q;
 
int calc(int k, int x) { return k + (x*(x+1)/2); }
 
bool isSafe(int cur) {
    if(cur < 0 or cur > NMAX) return 0;
    else return 1;
}
 
int main() {
    scanf("%d %d", &N, &K);
 
    memset(pos, -1, sizeof(pos));
    pos[K] = 0;
    for(int i=1;K+i<=NMAX;i++) {
        K += i;
        pos[K] = i;
    }
 
    ret = NMAX;
    check[N][0] = 1;
    q.push({N, 0});
    while(!q.empty()) {
        cur = q.front().first;
        x = q.front().second;
        q.pop();
 
        // 종료
        if(pos[cur]>=0 and x <= pos[cur] and pos[cur]%2 == x%2) {
            ret = min( ret, pos[cur] );
 
            continue;
        }
 
        // 탐색
        curK = calc(K, x);
        if(isSafe(cur-1) and !check[cur-1][(x+1)%2]) {
            q.push({cur-1, x+1});
            check[cur-1][(x+1)%2] = 1;
        }
 
        if(isSafe(cur+1) and !check[cur+1][(x+1)%2]) {
            q.push({cur+1, x+1});
            check[cur+1][(x+1)%2] = 1;
        }
 
        if(isSafe(cur*2) and !check[cur*2][(x+1)%2]) {
            q.push({cur*2, x+1});
            check[cur*2][(x+1)%2] = 1;
        }
    }
 
    if(ret == NMAX) printf("-1");
    else printf("%d", ret);
}

후기

특정 위치의 방문 여부를 홀/짝으로 나눠서 한다는 걸 생각하는데 시간이 좀 걸린 문제입니다. 생각보다 그리 단순하지 않아서 재미있던 문제라고 생각합니다. BFS를 연습하는 사람에게 추천합니다.