[백준 17071] 숨바꼭질 5

🔗 알고리즘 문제

방문 체크 조건을 생각해내기가 어려웠던 BFS문제. 그래프 탐색 문제를 많이 풀어보며 실력이 늘었다고 생각했지만, 문제를 조금만 꼬아도 머리가 멈춰버리는 느낌이다... 좀 더 연습해야겠다!

문제 분석

이 문제는 수빈이가 동생을 잡는데까지 몇 초가 걸리는지 알아내는 문제이다.

1초가 지날 때 마다 수빈이와 동생의 위치가 변경되게 되는데, 수빈이는 X-1, X+1, 2X의 칸으로 이동할 수 있고, 동생은 매초마다 X+T의 위치로 이동하게 된다.

발상 & 알고리즘 설계

이 문제는 방문 체크를 설계하기가 까다로웠다. 처음에는 기본적인 BFS로 구현하였다. 잘 작동되나 싶었지만, 다음과 같은 테스트케이스에서 문제가 발생했다.

n:17 k:5 해당 경우인데 이 경우에는 17 -> 16 -> 15 -> 14 -> 15 다음과 같이 4번만에 동생을 잡을 수 있는게 정답이다. 하지만 내가 구현한 방법으로는 도저히 중복된 칸으로 돌아올 때를 처리할 수 없었다.

방문 체크를 아예 하지 않고 모든 경우를 탐색한다면, 정답을 재대로 출력할 순 있지만 너무 많은 중복값들이 생기게되어 알고리즘 자체가 터져버리고 말았다.

방문 체크를 효율적으로 진행하며, 문제를 해결할 수 있는 방법을 찾기위해 모든 경우의 수를 적어가며 고민하던 중 문제에서 한가지 규칙을 발견할 수 있었다.

바로, 수빈이는 +1, -1로 이동할 수 있기에 T번째에 도착한 칸에는 T+2, T+4... 번째에도 도착할 수 있다는 것이다. 즉 짝수번째에 도달한 칸에는 앞으로 모든 짝수번째에 다시 도달할 수 있고, 홀수번째에 도달한 칸에는 앞으로 모든 홀수번째에 다시 도달할 수 있다는 것이다.

그렇다면 짝수, 홀수를 각각 최초 도착 일시만 방문체크를 해주고 탐색 종료 조건을 idx와 target이 일치할 때가 아닌 동생이 짝수번째에 도달한 칸을 플레이어도 짝수번째에 도달하였는지, 홀수번째에 도달한 칸을 플레이어도 홀수번째에 도달하였는지를 검사해주면 된다!

코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

class Val{
public:
    int idx;
    int target;
    int cost;
};

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

    int n;
    int k;

    int visited[2][500001] = {};
    memset(visited, -1, sizeof(visited));

    cin >> n >> k;

    queue<Val> q;
    q.push({ n, k, 0 });

    while(!q.empty()){
        Val cur = q.front();
        q.pop();

        if(cur.target > 500000)
            continue;
        if(cur.idx < 0 || cur.idx > 500001)
            continue;
        if(visited[cur.cost % 2][cur.idx] != -1)
            continue;

        visited[cur.cost % 2][cur.idx] = cur.cost;

        if(visited[cur.cost % 2][cur.target] != -1){
            cout << cur.cost;
            return 0;
        }

        q.push({ cur.idx + 1, cur.target + cur.cost + 1, cur.cost + 1 });
        q.push({ cur.idx - 1, cur.target + cur.cost + 1, cur.cost + 1 });
        q.push({ cur.idx * 2, cur.target + cur.cost + 1, cur.cost + 1 });
    }

    cout << -1;
}