[백준] 12851번: 숨바꼭질2 / C++

✏️ 문제 링크

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

12851번: 숨바꼭질 2

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 코드 (BFS)

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define MAX 100001

vector<bool> v(MAX, false);
vector<int> ans;
int N, K;

void bfs(int s){
    
    queue<pii> q;//position and depth
    q.push({s, 0}); v[s]=true;
    
    while(!q.empty()){
        
        pii cur=q.front(); q.pop();
        int pos=cur.first; int depth=cur.second;
        // cout<<"pos: "<<pos<<" depth: "<<depth<<"\n";
        
        v[pos]=true;
        
        if(pos==K){// found sister
            ans.push_back(depth);
            continue;
        }

        if(pos-1>=0 and !v[pos-1]) q.push({pos-1, depth+1});
        if(pos+1<MAX and !v[pos+1])q.push({pos+1, depth+1});
        if(pos*2<MAX and !v[pos*2])q.push({pos*2, depth+1});
        
    }
}



int main(){
    cin>>N>>K;
    bfs(N);
    sort(ans.begin(), ans.end());
    int mn=ans[0];
    int cnt=0;
    for(auto a: ans){
        if(a!=mn)break;
        cnt++;
    }
    cout<<mn<<"\n"<<cnt;
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐