[Algorithm] Baekjoon 17071번 : 숨바꼭질 5

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

17071번: 숨바꼭질 5

struct Node
{
    int position;
    int targetPosition;
    int time;
};
 
int n, k;
bool visited[500001][2] = { false };
 
int BFS()
{
    queue<Node> q;
    q.push({ n,k,0});
 
    visited[n][0] = true;
 
    while (!q.empty())
    {
        int curPosition = q.front().position;
        int curTargetPosition = q.front().targetPosition;
        int curTime = q.front().time;
 
        q.pop();
 
        if (curTargetPosition > 500000) return -1;
 
        int nextTargetPosition = curTargetPosition + curTime + 1;
 
        if (curPosition == curTargetPosition || visited[curTargetPosition][curTime % 2])
        {
            return curTime;
        }
 
        for (int nextPosition : {curPosition - 1, curPosition + 1, curPosition * 2})
        {
            if (nextPosition >= 0 && nextPosition <= 500000 && !visited[nextPosition][(curTime + 1) % 2])
            {
                visited[nextPosition][(curTime + 1) % 2] = true;
                q.push({ nextPosition, nextTargetPosition, curTime + 1 });
            }
        }
        
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    cout << BFS();
}

 

플레문제는 처음 풀어봤다. BFS문제라 그래도 좀 친숙해서 시도했는데 결과적으론 내가 생각치 못한 풀이로 풀리는 문제였다.

 

이 문제가 좀 더 난이도가 높은 이유는, 언니의 이동이 -1과 +1이 가능하다는 것과 동생이 계속 이동한다는 것이다.

단순히 고정된 타겟지점에 대해 최소횟수를 구하는거라면 DP값을 기록하면서 진행하면 되기 때문에 어렵지 않다.

다만, 동생은 계속 이동하기 때문에 다른 방식으로 생각해야 한다.

 

먼저 이 문제에서 특정지점에 언니가 언제 도착했는지는 더이상 중요한 문제가 아니다.

다만, 해당 지점에 짝수초에 도착했었는지 여부와 홀수초에 도착했었는지 여부가 중요하다.

그렇기 때문에 visited는 1차원이 아닌 2차원 배열이다. 홀수초, 짝수초에 각각 도달했었는지에 대한 여부만이 중요하다.

혹시나 헷갈릴 수 있는 사람을 위해 말하자면 어떠한 특정지점은 홀수,짝수초 둘 다 충분히 도달할 수 있다.

 

결과적으로 동생이 특정지점에 짝수초(10초)에 도착했을 때, 이미 언니가 그 전에 짝수초(4초)에 도착했던 적이 있더라면, 언니는 동생의 도착시간인 10초에도 특정지점에 있는게 가능하다.

 

왜? +1을 한다음 -1을 하면 되니까 (제자리)

그리고 이 +1,-1은 2초가 소모가 된다. 그래서 동생이 홀수초에 도착했을 때 언니도 홀수초에 도착한적이 있어야 한다.

왜냐하면 홀수초 - 홀수 = 2의배수. 짝수초 - 짝수초 = 2의 배수니까. (제자리 왔다갔다가 가능하다는 의미)

 

만약 특정지점에 동생이 13초에 도착했는데, 언니는 이전에 같은지점에 10초에 도착했다?

그러면 언니는 13초에 특정지점에 다시 도달할 수 없다. +1,-1 각각 쌍을 맞춰야하기 때문이다.

 

이렇게 로직을 구성하면 각 지점에 대해 두번의 접근만이 허용되며 노드를 뿌리는것도 두번씩만 뿌리기 때문에 메모리나 시간제한에 걸리지 않는다.