백준 1697번 - 숨바꼭질

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

수빈이가 동생을 찾기 위해 현재 위치에서 뒤로, 앞으로, 2배만큼 갈 수 있다.
3가지의 경우를 고려하여 queue에 담은 다음에 동생의 위치에 이를 때 시간을 출력하는 bfs 문제이다.



위의 3가지 경우를 push할 때 고려해야 할 점이 있다.
먼저 해당 위치를 이전에 방문을 했는지의 유무이다. visited라는 변수를 통해서 방문했을 경우 
다시 push 하지 않는다면 메모리 초과로 답을 구하지 못하게 된다.


다음으로 해당 위치에서 -1만큼 이동하는 경우에는 그 위치가 0 이상인지를 확인해야 한다. 

여기서 주의해야 할 점은 if 문을 통해서 확인할 때 먼저 0 이상인지를 확인하고 방문을 했는지 검사해야 한다. 

만약 방문을 했는지부터 검사한다면 visited의 배열 값에 음수가 들어갈 수도 있기 때문에 런타임 오류가 발생하게 된다.



마지막으로 두 배만큼 이동하는 경우이다.
현재의 위치에서 두 배만큼 이동하는 것이 옳은지를 먼저  판단해야 한다. 

무작정 2배만큼 이동한다면 그만큼 필요 없는 경우를 확인해야 하는 시간이 길어지기 때문이다.

수빈이의 위치를 n, 목표지점을 k라고 했을 때 
n*2-k가 k-n보다 작을 때 두 배만큼 이동한 경우를 push 해줬다.


예를 들어
n이 6이고 k가 11일 때 n을 두 배 해준 12에서 -1을 하면 두 번 만에 갈 수 있다.
그러나 n이 6이고 k가 8일 경우에는 n을 두 배 해준 뒤에 8을 가기 위해 4번을 빼는 것보다
6에서 8로 +2만큼 가는 것이 더욱 빠르기 때문에 n*2-k와 k-n을 비교해서 전자가 더 작을 때만 현재의 위치에서 두 배를 해준 경우를 push해주었다.


마지막으로 방문한 배열의 크기는 N이나 K가 가장큰 100000에서 두 배를 하는 경우를 고려하여 
200000으로 잡아주었다.

#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    
    int N,K;
    cin>>N>>K;
    
 
    int visited[200001]={0};
    queue<pair<int,int>> q;
    q.push(make_pair(0,N));
    
    visited[N]++;
    
    while(!q.empty()){
        int cnt=q.front().first;
        int pos=q.front().second;
        q.pop();
        
        if(pos==K){
            cout<<cnt<<endl;
            break;
        }
        
        if(!visited[pos+1]){
            q.push(make_pair(cnt+1,pos+1));
            visited[pos+1]++;
        }
        
        if(pos-1>=0 && !visited[pos-1]){
            q.push(make_pair(cnt+1,pos-1));
            visited[pos-1]++;
        }
        
        if(pos*2-K<=K-pos && !visited[pos*2]){
            q.push(make_pair(cnt+1,pos*2));
            visited[pos*2]++;
        }
 
    }
    return 0;
}