[17071] 숨바꼭질 5

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

17071번: 숨바꼭질 5

<문제>

일반적인 형태의 bfs로 해결할 수 있었던 [1697]숨바꼭질과 달리, 이 문제는 동생의 위치가 고정적이지 않다.

단순한 bfs로 구현하면 최적해를 찾지 못하거나, 찾더라도 시간초과가 나오는 구조로 되어있는듯 하다.

 

수빈이가 x+1로 이동하고, 다시 x-1로 이동하게 된다면

최종적으로 2초의 시간을 사용하여 제자리로 돌아오는형태가 된다.

즉, 이 문제에서 연산은 아래의 세가지가 주어져 있는데,
(x-1) (x+1) (2*x)

이 3가지는 가중치가 1인 연산이고 여기에 가중치2에 제자리에 머무르는 연산까지 총 4가지 연산이 있다고 생각하자.

 

input : 5 7 일때, 10의 위치을 1의 비용을 사용하여 도달할 수 있다면

10이라는 위치는 3, 5, 7...과 같은 1부터의 홀수의 비용을 사용하여 항상 도달할 수 있는 상태로 표시해주고

20이라는 위치는 2부터 시작하는 짝수의 비용으로 도달할 수 있다고 표시해줄 것이다.

이를 visit[노드][2]의 int형 배열에 최적해를 저장해줄 것이다.  

위의 10과 20의 위치는 아래처럼 생각할 수 있다. 2번째 index가 0일땐 짝수, 1일땐 홀수로 생각하면 되겠다.

visit[10][1] = 3
visit[20][0] = 2

 

위 과정을 bfs를 사용해 전처리해주어, 최종적인 결과를 2차원 visit에 업데이트 해줬다면 이제 어려운 부분은 끝났다.

i초후의 동생의 위치를 담는 vector를 간단하게 구성해줄 수 있을것이다.

이 vector를 순회하며, i초후의 동생의 위치가 pos라고 할때,

visit[pos][i%2] <= i를 만족하는 최소의 i가 곧 정답이다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int MAX = 500000;
typedef struct {
    int x, turn;
} state;
int n, k, visited[2 * MAX + 1][2];
queue<state> q;
int main(void) {
    int i, j;
    cin >> n >> k;
    fill(&visited[0][0], &visited[MAX + 1][2], -1);
    q.push({n, 0});
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.x > MAX || cur.x < 0) continue;
        if (visited[cur.x][cur.turn % 2] != -1) continue;
        visited[cur.x][cur.turn % 2] = cur.turn;
        q.push({cur.x - 1, cur.turn + 1});
        q.push({cur.x + 1, cur.turn + 1});
        q.push({2 * cur.x, cur.turn + 1});
    }
    for (i = k, j = 0; i <= MAX; j++, i = i + j) {
        if (visited[i][j % 2] != -1 && visited[i][j % 2] <= j) {
            cout << j;
            return 0;
        }
    }
    cout << "-1";
    return 0;
}

14-23 : bfs를 사용한 전처리, 수빈이가 도달할 수 있는 노드의 최단거리를 업데이트한다.

23-29 : j초후의 동생의 위치를 i에 저장; 최소값을 찾아야 하므로 상향식