13549번_숨바꼭질 3

문제 출처 : https://www.acmicpc.net/problem/13549

 

<C++Code>

#include<iostream>
#include<queue>
#define MAX 100001
using namespace std;
int n,m;
int v[MAX];
queue<pair<int,int> > q;
int cnt;
 
int bfs(int start)
{
    q.push({0,start});
    v[start]=1;
    
    while(!q.empty())
    {
        int size=q.size();
        for(int i=0;i<size;i++)
        {
            int po=q.front().second;
             cnt=q.front().first;
             q.pop();
         
    
        if(po==m)
        {
            cout<<cnt<<endl;
        exit(0);
        }
            
        
        int next=po*2;
        while(next<=100000&&v[next]==0)
        {
            q.push({cnt,next});
            v[next]=1;    
        }
    
        next=po-1;
        if(next>=0&&v[next]==0)
        {
            q.push({cnt+1,next});
            v[next]=1;
        }
        next=po+1;
        if(next<=100000&&v[next]==0)
        {
            q.push({cnt+1,next});
            v[next]=1;
        }
}
    }
}
 
 
 
int main(void)
{cin>>n>>m;
bfs(n);
cout<<cnt<<endl;
    return 0;
    
}

<C++Code>

 

#include<iostream>
#include<queue>
#include<string.h>
#define max 100001
using namespace std;
queue<int> q;
queue<int> w;
int v[max];
bool c[max];
 
int main(void)
{
    int n,m;
    cin>>n>>m;
    memset(v,-1,sizeof(v));
    q.push(n);
    v[n]=0;
    c[n]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        //cout<<x<<' ';
        if(x==m)
        {
            break;
        }
        int next=x*2;
        if(!c[next]&&next<=100000)
        {
            q.push(next);
            v[next]=v[x];
            c[next]=true;
            
        }
        next=x-1;
        if(!c[next]&&next>=0)
        {
            w.push(next);
            v[next]=v[x]+1;
            c[next]=true;
            
        }
        next=x+1;
        if(!c[next]&&next<=100000)
        {
            w.push(next);
            v[next]=v[x]+1;c[next]=true;
            
        }
        if(q.empty())
        {
            q=w;
            w=queue<int> ();
            
        }
    }
    cout<<v[m]<<' ';
    
    
    return 0;
    
}