숨바꼭질

오랜만에 푸는 백준이다. 실버 1 문제에 이렇게 좋은 문제가 있을 줄 몰랐다. 이 문제는 bfs를 활용해서 모든 경우의 수를 탐색하고 가장 최단 거리를 찾아야 하는 문제다.

그런데 이때 잊으면 안되는건 bound도 신경 써줘야 하고 내가 갔던 포인트를 visited 로 바로 박으면 큰일 난다.

내가 방문한 숫자의 포인트도 다시 방문할 수 있다는 것을 알아야지 문제를 풀 수 있고 이걸 나는 2차원 배열로 확인 해줬다.

만약 같은 숫자여도 누군가는 +1 혹은 -1 혹은 순간이동으로 갈 수 있어서 이걸 모두 0, 1 혹은 2로 구분 지어주고 bfs를 하니 통과되었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, K; 
bool visited[100001][3]; 

struct Person{
    int currLoc, currDist; 
};

void Input(){
    cin >> N >> K; 
}


void Solution(){
    queue<Person> q;
    q.push({N,0}); 

    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Person p = q.front();
            q.pop(); 

            int currLoc = p.currLoc, currDist = p.currDist; 

            if(currLoc == K){
                cout << currDist; 
                return; 
            }

            if(currLoc - 1 >= 0 && !visited[currLoc-1][0]){
                visited[currLoc-1][0] = true;
                q.push({currLoc-1, currDist+1}); 
            }

            if(currLoc + 1 <= 100000 && !visited[currLoc+1][1]){
                visited[currLoc+1][1] = true;
                q.push({currLoc+1, currDist+1}); 
            }

            if(2 * currLoc <= 100000 && !visited[2 * currLoc][2]){
                visited[2 * currLoc][2] = true; 
                q.push({2 * currLoc, currDist + 1}); 
            }
        }
    }

    cout << -1; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt.txt", "r", stdin);
    Solve();
    return 0;

}